本文最后更新于:2020年4月20日 凌晨
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6442
定义序列
它的指数型生成函数为
设是一个常数
定义序列,
定义两个生成函数的卷积(原题面省略了阶乘,可能是写错了?)
现在给三个正整数,求的前的系数乘上后的结果
赛中走了很多弯路,思路大概是这样的
首先用泰勒展开,可以看出
所以
第n项系数为
类似斐波那契数列也可以强行求出线性递推的式子然后矩阵快速幂,就是推得比较难受罢了==
更快的方法
不用泰勒展开,直接用二项式定理类似的凑一下就可以得到第项系数的式子,最后也不用推递推式,答案就是中去掉整数项,直接快速幂就做完了。
赛中代码:
#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));
}
}
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!