题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6442
定义序列{a}=(a0,a1,a2,…)
它的指数型生成函数为g{a}(x)=∑i=0∞i!aixi
设c是一个常数
定义序列{uc}=(c0,c1,c2,…),{ec}=(0,c1,0,c3,0,c5,…)
定义两个生成函数g{a},g{b}的卷积G(x)=(g{a}∗g{b})(x)=∑n=0∞(∑i+j=ni!aij!bj)xn(原题面省略了阶乘,可能是写错了?)
现在给三个正整数n,A,B,求G(x)=guA∗geB的xn前的系数乘上n!后的结果
赛中走了很多弯路,思路大概是这样的
首先用泰勒展开,可以看出
guA=eAx,geB=21(eBx−e−Bx)
所以G(x)=guA∗geB=21(e(A+B)x−e(A−B)x)
第n项系数为2(A+B)n−(A−B)n
类似斐波那契数列也可以强行求出线性递推的式子然后矩阵快速幂,就是推得比较难受罢了==
更快的方法
不用泰勒展开,直接用二项式定理类似的凑一下就可以得到第n项系数的式子,最后也不用推递推式,答案就是(A+B)n=x+yB中去掉整数项x,直接快速幂就做完了。
赛中代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| #include<bits/stdc++.h> using namespace std; typedef long long ll; ll a,b,n,mod; struct matrix { ll mx[2][2]; matrix() { memset(mx,0,sizeof(mx)); } void clear() { memset(mx,0,sizeof(mx)); } void init() { memset(mx,0,sizeof(mx)); mx[0][0]=mx[1][1]=1; } friend matrix operator *(const matrix &a,const matrix &b) { matrix c; for(int i=0;i<2;++i) for(int k=0;k<2;++k) for(int j=0;j<2;++j) c.mx[i][j]=(c.mx[i][j]+a.mx[i][k]*b.mx[k][j])%mod; return c; } }A,ans; int main() { int T; scanf("%d",&T); while(T--) { scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&mod); ans.init(); A.mx[0][0]=2*a%mod;A.mx[0][1]=1; A.mx[1][0]=(b-a*a%mod+mod)%mod;A.mx[1][1]=0; --n; while(n) { if(n&1) ans=ans*A; A=A*A; n>>=1; } ll pp=0; for(ll i=1;1LL*i*i<=b;++i) if(b%(i*i)==0) pp=i; printf("%d %I64d %I64d\n",1,ans.mx[0][0]*pp%mod,b/(pp*pp)); } }
|