生成函数(GF)

标签：ch 限制 函数 形式 生成 GF 不太好 frac

学了一点皮毛，暂时先写一篇博客寄存一下

定义：比较抽象的理解一下就是把一个限制条件的方案数转化成一个次冥函数的形式，再把一个次幂函数转化成某种限制条件下的方案数.......
大概是这么一个形式：

\[f(x)=a_{0}x^0+a_{1}x^1+a_{2}x^2+····· \]

还是举个例子吧：
你现在要离校回家了，但教练给你提了两个要求：\(1.回家的前3天有且仅有有一天学文化课。2.回家的奇数天有且仅有一天学奥赛\)，你现在到家了，你的mother又提了一个要求\(回家后的3的倍数天(包括第0天)有且仅有一天去和她去买东西\)，但这些在强迫症的你的眼里，你必须要求它们的日期之和为n，求你所有合法的方案的数数量。
啊~,这个东西显然是不太好做的，所以考虑引用我们刚刚提出的那个概念——生成函数！
我们设函数\(f_{1}\)表示第一个限制，则有：

\[f_{1}(x)=x+x^2+x^3 \]

同理我们可以把另外两个限制条件也通过函数的形式表现出来，即为:

\[f_{1}(x)=x+x^2+x^3 \]

\[f_{2}(x)=x+x^3+x^5+x^7+····· \]

\[f_{3}(x)=1+x^3+x^6+x^9+····· \]

显然的是要同时满足这几个限制条件就要把这几个函数乘起来，但这显然是不太好搞得，所以考虑把这几个函数化成封闭形式，则有：

\[f_{1}(x)=\frac{x^4-x}{x-1} \]

\[f_{2}(x)=\frac{x}{1-x^2} \]

\[f_{3}(x)=\frac{1}{1-x^3} \]

\[f_{1}(x)*f_{2}(x)*f_{3}(x)=\frac{(x^4-x)*x*1}{(x-1)*(1-x^2)*(1-x^3)} \]

\[=\frac{x^2}{(1-x)*(1-x^2)} \]

然后把这个式子化成多项式的形式即可，其中第\(n\)项的系数即为答案，但我举的这个例子好像不太好化，那就先不化了吧，这里提供一个方便转化的公式：

\[\sum_{n=0}^{\infty}C_{n+m}^{n}x^n=\frac{1}{(1-x)^{m+1}} \]

其中第\(n\)项的系数就是\(C_{n+m}^{n}\)，知道\(m\)后即可求出。
最后看一道能划开的例题吧：
luogu P10780 BZOJ3028 食物
具体过程就不说了，和我上面说的基本一致，贴个代码就行了

#include<iostream>
long long n,p=10007;
signed main(){
	char ch=getchar_unlocked();
	while(ch>='0'&&ch<='9'){
		n=(n*10+(ch^48))%p;
		ch=getchar_unlocked();
	}
	std::cout<<(n+2)*(n+1)*n*1668%p;
	return 0;
}

事实上推出来之后这代码似乎可有可无，润润润！

标签：ch,限制,函数,形式,生成,GF,不太好,frac
From： https://www.cnblogs.com/houburzyx/p/18375204