一种快速的常系数齐次线性递推算法

本文主要是介绍一种快速的常系数齐次线性递推算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

论文参考
https://arxiv.org/pdf/2008.08822.pdf

int t[N],p[N],q[N],dp[N],dq[N],ddp[N],ddq[N]; 
int coefficient(int n,int len)
{
	int v=inv(2),wn=ksm(h,(mo-1)/(2*len)),wm=inv(wn); 
	
	for(int i=0;i<len;i++)dp[i]=p[i],dq[i]=q[i];
	ntt(dp,len,+1);ntt(dq,len,+1);
	while(n) 
	{
		//ddp ddq
		for(int i=0;i<len;i++)ddp[2*i]=dp[i],ddq[2*i]=dq[i];
		for(int i=0,w=1;i<len;i++,w=1ll*w*wn%mo)p[i]=1ll*p[i]*w%mo,q[i]=1ll*q[i]*w%mo;
		ntt(p,len,+1);ntt(q,len,+1);
		for(int i=0;i<len;i++)ddp[2*i+1]=p[i],ddq[2*i+1]=q[i];
		//p dp
		for(int i=0;i<2*len;i++)t[i]=1ll*ddp[i]*ddq[i^len]%mo;
		if(n&1)for(int i=0,w=1;i<2*len;i++,w=1ll*w*wm%mo)t[i]=1ll*t[i]*w%mo;
		for(int i=0;i<len;i++)t[i]=1ll*v*inc(t[i],t[i+len])%mo,dp[i]=t[i];
		ntt(t,len,-1);for(int i=0;i<len;i++)p[i]=t[i];	
		//q dq
		for(int i=0;i<2*len;i++)t[i]=1ll*ddq[i]*ddq[i^len]%mo;
		for(int i=0;i<len;i++)t[i]=1ll*v*inc(t[i],t[i+len])%mo,dq[i]=t[i];
		ntt(t,len,-1);for(int i=0;i<len;i++)q[i]=t[i];
		
		n>>=1; 
	}
	return 1ll*p[0]*inv(q[0])%mo;
}
int recurrence(int *f,int *g,int n,int k)
{
	int len=1;
	while(len<(n+1))len<<=1;
	for(int i=0;i<len;i++)p[i]=q[i]=0; 
	q[0]=1;for(int i=1;i<=n;i++)q[i]=dec(0,g[i]);
	
	for(int i=0;i<n;i++)a[i]=f[i];
	b[0]=0;for(int i=1;i<=n;i++)b[i]=g[i];
	poly_mul(len,len); 
	for(int i=0;i<n;i++)p[i]=dec(f[i],a[i]);
	
	return coefficient(k,len);
}

这篇关于一种快速的常系数齐次线性递推算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！