HDU3734 Blocks

####Description

Panda has received an assignment of painting a line of blocks. Since Panda is such an intelligent boy, he starts to think of a math problem of painting. Suppose there are N blocks in a line and each block can be paint red, blue, green or yellow. For some myterious reasons, Panda want both the number of red blocks and green blocks to be even numbers. Under such conditions, Panda wants to know the number of different ways to paint these blocks.

####Input

The first line of the input contains an integer T(1≤T≤100), the number of test cases. Each of the next T lines contains an integer N(1≤N≤10^9) indicating the number of blocks.

####Output

For each test cases, output the number of ways to paint the blocks in a single line. Since the answer may be quite large, you have to module it by 10007.

####Sample Input

2
1
2
####Sample Output

2
6
####Source

PKU Campus 2009 (POJ Monthly Contest – 2009.05.17), Simon

根据题目，我们构造指数生成函数，每一项前的系数表示涂色i个块的方案。（如果不知道指数生成函数可以简单了解：[传送门](https://wenku.baidu.com/view/7b5cfad126fff705cc170a7b.html)，[另一个传送门](http://blog.leanote.com/post/rockdu/TX03)）因为只为偶数，所以偶数次上的系数为1，其余为0。没有只为偶数限制的，所有系数都是1.得到：$$G(x)=[(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}...)^2]\cdot [(1+\frac{x^2}{2!}+\frac{x^4}{4!}+...)^2]$$
通过化简可以得到答案的生成函数为如下式子：
$$G(x) = (\sum^{\frac{n}{2}}_{i = 0}\frac{x^{i*2}}{(i*2)!})^2 \cdot (\sum^{n}_{i = 0}\frac{x^{i}}{i!})^2$$
由 泰勒展开：$$G(x) = (\frac{1}{2}(e^{x}-e^{-x}))^2 \cdot e^{2x}$$
$$G(x) = \frac{1}{4}(e^{2x}-2 +e^{-2x}) \cdot e^{2x}$$
$$G(x) = \frac{1}{4}(e^{4x}-2e^{2x} +1)=\frac{1}{4}(e^{2x}-1)^2$$
逆运算得：$$G(x)=\frac{1}{4}\sum^{\infty}_{i=0}(4^i+2\times2^i)\cdot x^i$$
那么每一项的系数可以用快速幂直接求解。
代码如下：
```
#include<cstdio>
#define LL long long
using namespace std;
LL n;
int t, mod = 10007;
LL fpow(LL a, LL b, LL c) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % c;
		a = a * a % c;
		b >>= 1;
	}
	return ans;
}
int main() {
	scanf("%d", &t);
	while(t--) {
		scanf("%lld", &n);
		printf("%lld\n", (fpow(4, n - 1, mod) + fpow(2, n - 1, mod)) % mod);
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链