题意

链接

长度为\(n\)的序列，用红黄蓝绿染色，其中红黄只能是偶数，问方案数

Sol

生成函数入门题

任意的是\(e^x\)，偶数的是\(\frac{e^x + e^{-x}}{2}\)

最后化完是\(\frac{e^{4x} + 2e^{2x}+1}{4} = \frac{4^n+2 * 2^{n+1}}{4}\)(\(\frac{1}{4}\))相当于常数项

#include<iostream>

#include<cstdio>

using namespace std;

const int mod = 10007;

int fp(int a, int p) {

	int base = 1;

	while(p) {

		if(p & 1) base = 1ll * base * a % mod;

		a = 1ll * a * a % mod; p >>= 1;

	}

	return base;

}

void solve() {

	int n; cin >> n;

	cout << 1ll * (fp(4, n) + 2ll * fp(2, n) % mod) % mod * fp(4, mod - 2) % mod << '\n';

}

int main() {

	int T; cin >> T;

	for(; T--; solve());

	return 0;

}