「POJ 3734」Blocks-生成函数

链接

POJ 3734

题意

有一排砖,数量为 nn,有红蓝绿黄 44 种颜色,其中染成红和绿颜色的砖块的数量必须为偶数个,求可有多少种染色方案。

题解

构造指数型生成函数

Y(x)=B(x)=i=0xii!Y(x) = B(x) = \sum_{i = 0} ^ {\infty} \frac {x ^ i} {i!}R(x)=G(x)=i=0x2i(2i)!R(x) = G(x) = \sum_{i = 0} ^ {\infty} \frac {x ^ {2i}} {(2i)!}

根据泰勒展开有

ex=i=0xii!e ^ x = \sum_{i = 0} ^ {\infty} \frac {x ^ i} {i!}ex=i=0(x)ii!e ^ {-x} = \sum_{i = 0} ^ {\infty} \frac {(-x) ^ i} {i!}

R(x)=G(x)=ex+ex2R(x) = G(x) = \frac {e ^ x + e ^ {-x}} {2}

答案为

Y(x)B(x)R(x)G(x)=(ex)2(ex+ex2)2=e4x+2e2x+14=i=04i+22i4xii!=4n1+2n1\begin{aligned}Y(x)B(x)R(x)G(x) &= (e ^ x) ^ 2(\frac {e ^ x + e ^ {-x}} {2}) ^ 2 \\ &= \frac {e ^ {4x} + 2e ^ {2x} + 1} {4} \\ &= \sum_{i = 0} ^ {\infty} \frac {4 ^ i + 2 * 2 ^ i} {4} \frac {x ^ i} {i!} \\ &= 4 ^ {n - 1} + 2 ^ {n - 1} \end{aligned}

代码

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
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「POJ 3734」Blocks 29-07-2017
* 生成函数
* @author xehoth
*/
#include <iostream>
const int MOD = 10007;
inline int modPow(int a, int b, int c) {
register int ret = 1;
for (; b; b >>= 1, a = a * a % c) (b & 1) ? ret = ret * a % c : 0;
return ret;
}
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
register int t, n;
for (std::cin >> t; t--;) {
std::cin >> n;
std::cout << (modPow(4, n - 1, MOD) + modPow(2, n - 1, MOD)) % MOD
<< '\n';
}
return 0;
}
文章目录
  1. 1. 链接
  2. 2. 题意
  3. 3. 题解
  4. 4. 代码