传送门
生成函数的模板题
前置知识：
[sum_{i=0}^{+infty}x^i=frac{1}{1-x}
]
其实就是等比数列求和公式，这就是公比为(x)的等比数列，然后取(xin(-1,1))
也就是你只要会等比数列求和就行了
也就有
[(1+x+x^2+x^3+x^4+...)^k=(1-x)^k
]
然后还有一个结论，就是((1+x+x^2+x^3+x^4+...)^k)的第(i)项系数就是(inom{i+k-1}{k-1})
证明的话插板法就好了
承德汉堡：(frac{1}{1-x^2})
可乐：(frac{1-x^2}{1-x})
鸡腿：(frac{1-x^3}{1-x})
蜜桃多：(frac{x}{1-x^2})
鸡块：(frac{1}{1-x^4})
包子：(frac{1-x^4}{1-x})
土豆片炒肉：(frac{1-x^2}{1-x})
面包：(frac{1}{1-x^3})
然后乘起来就是(frac{x}{(1-x)^4})
设
[f(x)=frac{x}{(1-x)^4}\
f(x)=x(1+x+x^2+x^3+...)^4
]
那么我们要求的也就是(f(x))的第(n-1)项系数，也就是(inom{n+2}{3})
实现的话其实也没必要写高精度，读入的时候按位读，边读边模就好了
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e3+10,mod=10007,inv=1668;
int n,len,m=1;char a[maxn];
int main()
{
scanf("%s",a+1),len=strlen(a+1);
for(rg int i=len;i;i--){
n=(n+m*(a[i]-'0'))%mod;
m=m*10%mod;
}
printf("%d
",n*(n+1)%mod*(n+2)%mod*inv%mod);
}