2018.12.30 bzoj3028: 食物(生成函数)

传送门

生成函数模板题。


我们直接把每种食物的生成函数列出来:

承德汉堡:1+x2+x4+...=11−x21+x^2+x^4+...=\frac 1{1-x^2}1+x2+x4+...=1−x21​

可乐:1+x=1−x21−x1+x=\frac{1-x^2}{1-x}1+x=1−x1−x2​

鸡腿:1+x+x2=1−x31−x1+x+x^2=\frac{1-x^3}{1-x}1+x+x2=1−x1−x3​

蜜桃多:x+x3+x5+...=x(1+x2+x4+...)=x1−x2x+x^3+x^5+...=x(1+x^2+x^4+...)=\frac x{1-x^2}x+x3+x5+...=x(1+x2+x4+...)=1−x2x​

鸡块:1+x4+x8+x12+...=11−x41+x^4+x^8+x^{12}+...=\frac 1{1-x^4}1+x4+x8+x12+...=1−x41​

包子:1+x+x2+x3=1−x41−x1+x+x^2+x^3=\frac{1-x^4}{1-x}1+x+x2+x3=1−x1−x4​

土豆片炒肉:1+x=1−x21−x1+x=\frac{1-x^2}{1-x}1+x=1−x1−x2​

面 包:1+x3+x6+x9+...=11−x31+x^3+x^6+x^9+...=\frac 1{1-x^3}1+x3+x6+x9+...=1−x31​

把所有的乘起来:f(x)=x(1−x)4=x(1+x+x2+...)4f(x)=\frac x{(1-x)^4}=x(1+x+x^2+...)^4f(x)=(1−x)4x​=x(1+x+x2+...)4

我们要求xnx^nxn的系数。

也就是求g(x)=(1+x+x2+...)4g(x)=(1+x+x^2+...)^4g(x)=(1+x+x2+...)4的xn−1x^{n-1}xn−1的系数。

相当于求将n−1n-1n−1拆成四个自然数的方案数,这个组合数学搞定Ans=Cn+23Ans=C_{n+2}^3Ans=Cn+23​

代码:

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
int n=0;
int main(){
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))n=((n<<3)+(n<<1)+(ch^48))%mod,ch=getchar();
	cout<<n*(n+1)%mod*(n+2)%mod*1668%mod;
	return 0;
}
上一篇:用apache和tomcat搭建集群,实现负载均衡


下一篇:MSSQL远程连接