正題

題目鏈接:http://poj.org/problem?id=3734

---

題目大意

用思種顏色給$n$個格子染色，要求前兩種顏色出現偶數次，求方案。

$1\le T\le 100,1\le n\le 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);} }

總結

以上是生活随笔為你收集整理的POJ3734-Blocks【EGF】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。