BZOJ3028:食物 生成函数

思路:

对于一个数列\(f_0,f_1,f_2,...\),我们可以对应的构造一个多项式函数\(f_0+f_1{x}+f_2{x^2}+...\),也即若我们可以知道函数的\(x^n\)项系数,就能知道\(f_n\).

一眼看起来并没有什么用处,实际上有的多项式函数可以化为十分简洁的形式.

例如\(f_0=f_1=f_2=...=1\),其对应的多项式函数为\(1+x+x^2+x^3+...\).

由于我们只在意式子的"型",因此可以利用方便的等比数列来表示:

\[\frac{1-x^{\infty}}{1-x}\]

若\(|x|<1\),则可以化为:

\[\frac{1}{1-x}\]

事实上我们不必在意\(x\)的范围,仅仅是看重形式便可以了.

对于这道题目的计数问题,我们仅需搞出所有限制的多项式,然后将它们相乘.

最终经过一些化简得到:

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

接下来有一种处理方法就是暴力泰勒展开(就是无限求导),感觉不可能找到规律(至少我是不会).

然后又一种方法就是再进行变形:

\[x(1+x+x^2+...)^4\]

求上式的\(x^n\)次项的系数.于是变成简单的组合数问题.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

char s[510];
int main(){
	scanf("%s",s);int len=strlen(s);register int i,j;
	int t=0;for(i=0;i<len;++i)t=(t*10+s[i]-'0')%10007;
	int res=t;res=res*(t+1)%10007,res=res*(t+2)%10007;
	res=res*1668%10007;
	printf("%d",res);
	return 0;
}