「POJ3734」Blocks

题意

有\(n\)个盒子和红，蓝，绿，黄四种颜色。使用这四种颜色对盒子进行染色，其中红色和绿色的数量必须为偶数，询问方案数

Solution

易知此题可以用指数型生成函数解决

对于红色和绿色，其\(EGF\)为

\[G_e(x)=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}\dots=\frac{e^x+e^{-x}}{2}\]

蓝色和黄色的\(EGF\)为

\[G_e(x)=1+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}\dots=e^x\]

乘起来可得

\[(\frac{e^x+e^{-x}}{2})^2*e^{2x}\]

\[=\frac{e^{4x}+2e^{2x}+1}{4}\]

我们知道\(\sum_{i=0}^{\infty}\frac{k^ix^i}{i!}=e^{kx}\)，\(n\)次项的系数为\(\frac{k^n}{n!}\)

忽略常数项，回带可得

\[\frac{4^n+2\times 2^n}{4n!}\]

乘上阶乘即为答案

\[\frac{4^n+2\times 2^n}{4}\]

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;template 
          
           void read(T &t){ t=0;int f=0;char c=getchar(); while(!isdigit(c)){f|=c=='-';c=getchar();} while(isdigit(c)){t=t*10+c-'0';c=getchar();} if(f)t=-t;}const int mod=10007;int T;int n;int fastpow(int a,int b){ int re=1,base=a; while(b) { if(b&1) re=re*base%mod; base=base*base%mod; b>>=1; } return re;}int main(){ read(T); while(T--) { read(n); printf("%d\n",(fastpow(4,n)+fastpow(2,n+1))%mod*fastpow(4,mod-2)%mod); } return 0;}