正题
题目链接:http://poj.org/problem?id=3734
题目大意
用思种颜色给\(n\)个格子染色，要求前两种颜色出现偶数次，求方案。
\(1\leq T\leq 100,1\leq n\leq 10^9\)
解题思路
反正是\(\text{EGF}\)的十分入门题了。
首先是\(\sum_{i=0}^{\infty}\frac{x^i}{i!}=e^x\)。
这题带标号计数所以求的是
\[(\sum_{i=0}^\infty\frac{x^{2i}}{2i!})^2\times (\sum_{i=0}^\infty\frac{x^i}{i!})^2
\]
嗯，后面那个就是\(e^x\)，前面那个怎么搞。
考虑点花里胡哨的东西，\(e^{-x}=\sum_{i=0}^\infty (-1)^i\frac{x^i}{i!}\)，然后我们就有
\[\sum_{i=0}^\infty\frac{x^{2i}}{2i!}=\frac{e+e^{-x}}{2}
\]
然后带进式子就是
\[(\frac{e^x+e^{-x}}{2})^2\times e^{2x}=\frac{e^{4x}+2e^{2x}+1}{4}
\]
然后\(e^{ax}=\sum_{i=0}^{\infty}a^i\frac{x^i}{i!}\)，所以展开一下项就是
\[[x^n]=\frac{4^n+2^n\times 2}{4}=4^{n-1}+2^{n-1}
\]
时间复杂度\(O(T\log n)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int P=10007;
int n,T;
int power(int x,int b){
int ans=1;
while(b){
if(b&1)ans=ans*x%P;
x=x*x%P;b>>=1;
}
return ans;
}
int main()
{
scanf("%d",&T);
while(T--){
scanf("%d",&n);n--;n%=(P-1);
printf("%d\n",(power(2,n)+power(4,n))%P);
}
}