BZOJ3028: 食物

###Description
明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！我们暂且不讨论他有多么NC，他又幻想了他应
该带一些什么东西。理所当然的，你当然要帮他计算携带N件物品的方案数。他这次又准备带一些受欢迎的食物，
如：蜜桃多啦，鸡块啦，承德汉堡等等当然，他又有一些稀奇古怪的限制：每种食物的限制如下：
承德汉堡：偶数个
可乐：0个或1个
鸡腿：0个，1个或2个
蜜桃多：奇数个
鸡块：4的倍数个
包子：0个，1个，2个或3个
土豆片炒肉：不超过一个。
面包：3的倍数个
注意，这里我们懒得考虑明明对于带的食物该怎么搭配着吃，也认为每种食物都是以‘个’为单位（反正是幻想嘛
），只要总数加起来是N就算一种方案。因此，对于给出的N,你需要计算出方案数，并对10007取模。
###Input
输入一个数字N，1<=n<=10^500

###Output
如题

###Sample Input
输入样例1
1
输入样例2
5
###Sample Output
输出样例1
1
输出样例2
35
###HINT
 
###Source

本题我们先写出所有的生成函数，并且先将无限的生成函数转换为有限形式以便于化简。关于泰勒展开可以看这一篇博客：
[初始生成函数(泰勒展开)](http://blog.leanote.com/post/rockdu/TX03)

写出来的式子：
$$(1 + x^2 + x^4 ...)(1 + x)(1 + x + x^2)(x^1 + x^3 + ...)(1 + x^4 + x^8 ...)(1 + x + x^2 + x^3)(1 + x)(1 + x^3 + x^6 ...)$$
$$\frac{1}{1 - x^2}(1 + x)(1 + x + x^2)\frac{x}{1 - x^2}\frac{1}{1 - x^4}(1 + x + x^2 + x^3)(1 + x)\frac{1}{1 - x^3}$$

注意到：
$$1 - x^n = (1 + x^1 + x^2 ... x^{n-1})(1 - x)$$
我们上面的式子就成了：
$$\frac{1}{{(1-x)}^4}$$
这个函数其实就是由$\frac{1}{1-x}$所表示的$1+x+x^2+x^3...$系数做四次前缀和得到的。可以求得第i项系数为：
$$\frac{n(n+1)(n+2)}{6}$$于是我们预处理6对10007的逆元就可以O(读入)做出来了

代码：
```
#include<cstdio>
#include<cctype>
using namespace std;
const int mod = 10007;
int x;
void read(int & n) {
 n = 0;char c = getchar();
 while(!isdigit(c)) c = getchar();
 while(isdigit(c)) n = (n * 10 + c - '0') % mod, c = getchar();
}
 
int main() {
 read(x);
 printf("%d", (((x * (x + 1)) % mod) * (x + 2) % mod) * 1668 % mod);
 return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链