2018 CCPC网络赛 GuGu Convolution

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6442

定义序列{a}=(a0,a1,a2,)\{a\}=(a_0,a_1,a_2,\dots)

它的指数型生成函数为g{a}(x)=i=0aii!xig_{\{a\}}(x)=\sum_{i=0}^{\infty}\frac{a_i}{i!}x^i

cc是一个常数

定义序列{uc}=(c0,c1,c2,)\{u_c\}=(c^0,c^1,c^2,\dots),{ec}=(0,c1,0,c3,0,c5,)\{e_c\}=(0,c^1,0,c^3,0,c^5,\dots)

定义两个生成函数g{a},g{b}g_{\{a\}},g_{\{b\}}的卷积G(x)=(g{a}g{b})(x)=n=0(i+j=naii!bjj!)xnG(x)=(g_{\{a\}}*g_{\{b\}})(x)=\sum_{n=0}^{\infty}(\sum_{i+j=n}\frac{a_i}{i!}\frac{b_j}{j!})x^n(原题面省略了阶乘,可能是写错了?)

现在给三个正整数n,A,Bn,A,B,求G(x)=guAgeBG(x)=g_{u_A}*g_{e_{\sqrt{B}}}xnx^n前的系数乘上n!n!后的结果

赛中走了很多弯路,思路大概是这样的

首先用泰勒展开,可以看出

guA=eAx,geB=12(eBxeBx)g_{u_A}=e^{Ax},g_{e_B}=\frac{1}{2}(e^{\sqrt{B}x}-e^{-\sqrt{B}x})

所以G(x)=guAgeB=12(e(A+B)xe(AB)x)G(x)=g_{u_A}*g_{e_{\sqrt{B}}}=\frac{1}{2}(e^{(A+\sqrt{B})x}-e^{(A-\sqrt{B})x})

第n项系数为(A+B)n(AB)n2\frac{(A+\sqrt{B})^n-(A-\sqrt{B})^n}{2}

类似斐波那契数列也可以强行求出线性递推的式子然后矩阵快速幂,就是推得比较难受罢了==

更快的方法

不用泰勒展开,直接用二项式定理类似的凑一下就可以得到第nn项系数的式子,最后也不用推递推式,答案就是(A+B)n=x+yB(A+\sqrt{B})^n=x+y\sqrt{B}中去掉整数项xx,直接快速幂就做完了。

赛中代码:

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));
}
}

2018 CCPC网络赛 GuGu Convolution
https://izard.space/2018/10/08/2018-CCPC网络赛-GuGu-Convolution/
作者
forever_you
发布于
2018年10月8日
许可协议