「POJ3734」Blocks

题意

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

Solution

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

对于红色和绿色，其EGFEGF为

Ge(x)=1+x22!+x44!+x66!⋯=ex+e−x2G_e(x)=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}\dots=\frac{e^x+e^{-x}}{2}

蓝色和黄色的EGFEGF为

Ge(x)=1+x22!+x33!+x44!⋯=exG_e(x)=1+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}\dots=e^x

乘起来可得

(ex+e−x2)2∗e2x(\frac{e^x+e^{-x}}{2})^2*e^{2x}

=e4x+2e2x+14=\frac{e^{4x}+2e^{2x}+1}{4}

我们知道∑i=0∞kixii!=ekx\sum_{i=0}^{\infty}\frac{k^ix^i}{i!}=e^{kx}，nn次项的系数为knn!\frac{k^n}{n!}

忽略常数项，回带可得

4n+2×2n4n!\frac{4^n+2\times 2^n}{4n!}

乘上阶乘即为答案

4n+2×2n4\frac{4^n+2\times 2^n}{4}

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;

template <typename T>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;
}