义乌便宜自适应网站建设厂家,网站平台搭建要多少,网站建设前的需求分析,软件开发专业专科所谓常系数齐次线性递推#xff0c;就是系数为常数的齐次线性递推。 #xff08;逃#xff09;
前言
sto Asta orz#xff01; 又是一个名字高大上#xff0c;实则小清新的算法#xff01;
解析
考虑一个 k 次的线性递推#xff1a; an∑i1kfian−ia_n\sum_{i1}^kf_… 所谓常系数齐次线性递推就是系数为常数的齐次线性递推。 逃
前言
sto Asta orz 又是一个名字高大上实则小清新的算法
解析
考虑一个 k 次的线性递推 an∑i1kfian−ia_n\sum_{i1}^kf_ia_{n-i}ani1∑kfian−i 不断的把高次的项按照定义式拆成低次项最终必然可以写成 ∑i0k−1piai\sum_{i0}^{k-1}p_ia_i∑i0k−1piai 的形式。 以最常见的斐波拉契为例f5f4f32f3f23f22f15f13f0f_5f_4f_32f_3f_23f_22f_15f_13f_0f5f4f32f3f23f22f15f13f0。 然后带入 a0...k−1a_{0...k-1}a0...k−1 的值计算即可。
注意到我们分解高次项的过程其实在本质上也就等价于令 xnx^nxn 不断向多项式 xk−f1xk−1−f2xk−2−...−fkx0x^k-f_1x^{k-1}-f_2x^{k-2}-...-f_kx^0xk−f1xk−1−f2xk−2−...−fkx0 取模的过程。 既然如此我们就可以直接使用类似于快速幂的方法不断把 xxx 平方并向上述的多项式取模即可。 暴力取模 O(k2logn)O(k^2\log n)O(k2logn)使用多项式科技可以做到 O(klogklogn)O(k\log k\log n)O(klogklogn)。
代码
过度封装非常严重常数极大。
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N2e5100;
const int mod998244353;
int n,m,k;
inline ll ksm(ll x,ll k){ll res1;while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}
int niv2ksm(2,mod-2);
int r[N];
void init(int n,int lim){lim1;int L0;while(limn) lim1,L;for(int i1;ilim;i) r[i](r[i1]1)|((i1)(L-1));
}
void NTT(ll *x,int lim,int op){for(int i0;ilim;i) if(ir[i]) swap(x[i],x[r[i]]);for(int l1;llim;l1){ll wksm(3,(mod-1)/(l1));if(op-1) wksm(w,mod-2);for(int st0;stlim;st(l1)){for(ll i0,now1;il;i,nownow*w%mod){ll ux[sti],vnow*x[stil]%mod;x[sti]uvmod?uv-mod:uv;x[stil]u-v0?u-vmod:u-v;}}}if(op-1){ll niksm(lim,mod-2);for(int i0;ilim;i) x[i]x[i]*ni%mod;}return;
}
void copy(ll *a,ll *b,int n,int lim){assert(nlim);memcpy(a,b,sizeof(ll)*n);fill(an,alim,0);return;
}
void mul(ll *a,ll *b,ll *c,int n,int m){static ll u[N],v[N];static int lim;init(nm-1,lim);copy(u,a,n,lim);copy(v,b,m,lim);NTT(u,lim,1);NTT(v,lim,1);for(int i0;ilim;i) c[i]u[i]*v[i]%mod;NTT(c,lim,-1);//for(int i0;inm-1;i) printf(%lld ,c[i]);putchar(\n);//putchar(\n);return;
}
void inv(ll *h,ll *f,int n){static ll t1[N],t2[N];static int lim;if(n1){f[0]ksm(h[0],mod-2);return;}inv(h,f,(n1)1);init(n1,lim);fill(f((n1)1),flim,0);copy(t1,f,n,lim);copy(t2,h,n,lim);NTT(t1,lim,1);NTT(t2,lim,1);for(int i0;ilim;i) t1[i](2*t1[i]-t1[i]*t1[i]%mod*t2[i]%modmod)%mod;NTT(t1,lim,-1);memcpy(f,t1,sizeof(ll)*n);return;
}
void chu(ll *f,ll *g,ll *q,ll *r,int n,int m){static ll F[N],G[N],ff[N],gg[N],Q[N],tmp[N];static int lim;--n;--m;init(nn,lim);copy(F,f,n1,lim);copy(ff,f,n1,lim);copy(G,g,m1,lim);copy(gg,g,m1,lim);reverse(F,F1n);reverse(G,G1m);inv(G,tmp,n-m1);mul(tmp,F,Q,n-m1,n-m1);reverse(Q,Qn-m1);//fill(Qn-m1,Qn1,0);for(int in-m1;in;i) Q[i]0;copy(q,Q,n-m1,lim);mul(Q,gg,tmp,n1,n1);for(int i0;in;i) r[i](ff[i]mod-tmp[i])%mod;return;
}ll F[N],G[N],Q[N],R[N];
void mul_mod(ll *x,ll *y,ll *Mod,int n){static ll t1[N],t2[N],t[N];static int lim;init(nn,lim);copy(t1,x,n,lim);copy(t2,y,n,lim);mul(t1,t2,t,n,n);chu(t,Mod,t1,t,2*n-1,n1);memcpy(x,t,sizeof(t));
}
ll LinearRecurrence(ll *a,ll *ff,int k,int n){static ll res[N],tmp[N],f[N];memset(tmp,0,sizeof(ll)*(k*25));memset(res,0,sizeof(ll)*(k*25));for(int i0;ik;i) f[i](mod-ff[k-i])%mod;f[k]1;tmp[1]1;res[0]1;while(n){if(n1){ mul_mod(res,tmp,f,k);}mul_mod(tmp,tmp,f,k);n1;}ll ans(0);for(int i0;ik;i) ans(ansa[i]*res[i])%mod;return ans;
}
ll f[N],a[N];
signed main() {
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();kread();for(int i1;ik;i) f[i](read()%modmod)%mod;for(int i0;ik;i) a[i](read()%modmod)%mod;printf(%lld\n,LinearRecurrence(a,f,k,n));return 0;
}
/*3 12 3 3 11 1
*/
