问题
设 \(\displaystyle a_n=\sum_{i=1}^{k}f_i\times a_{n-i}\)，已知 \(a_{0\sim k-1},f_{1\sim k}\)，求 \(a_n\)。
子问题
求解 \([x^k]\dfrac{P(x)}{Q(x)}\)，其中 \(P,Q\) 均不超过 \(n\) 次，\(k\) 比较巨大。
化为 \([x^k]\dfrac{P(x)Q(-x)}{Q(x)Q(-x)}\)。
显然可以发现分母的奇数项系数都是 \(0\) 了。
分讨 \(k\) 的奇偶性，如果 \(k\) 是奇数，就得到 \(\dfrac{xF(x^2)}{G(x^2)}\)；否则得到 \(\dfrac{F(x^2)}{G(x^2)}\)。这里 \(F\) 和 \(G\) 只需要使用两次多项式乘法和一些简单转换就能算出来。
然后现在问题就变成了计算 \([x^{k/2}]\dfrac{F(x)}{G(x)}\)，一直递归下去直到要求 \([x^0]\dfrac{F(x)}{G(x)}\) 即可，时间复杂度 \(O(n\log n\log k)\)。
原问题
现在我们只需要构造出来 \(P,Q\) 就好了。
一种构造是令 \(Q(x)=1-f_1x-f_2x^2-\cdots-f_kx^k\)，此时 \(\displaystyle[x^n]P(x)=a_n-\sum_{i=1}^{k}f_ia_{n-i}\)，不难发现其在 \(n\ge k\) 时为 \(0\)。
那么直接代入 \(P,Q,n\) 当作上面子问题的参数去解决即可。
代码
点击查看代码
#include<bits/stdc++.h>
#define int long long
// #define ll __int128
// #define ull unsigned int
#define N 300005
#define M 200005
#define K 20
// #define B 13331
#define mod 998244353
#define pii pair<int,int>
#define x first
#define y second
#define pct __builtin_popcount
#define mpi make_pair
#define pi acos(-1)
#define inf 2e18
#define poly vector<int>
using namespace std;
int Tc=1,n,k,rev[N],g=3,gg=332748118;
int ksm(int x,int y){int res=1;while(y){if(y&1)(res*=x)%=mod;(x*=x)%=mod;y>>=1;}return res;
}
void ntt(poly &a,int n,int t){for(int i=0;i<n;i++){if(i<rev[i]){swap(a[i],a[rev[i]]);}}for(int len=1;len<n;len<<=1){int w1=ksm((t==1?g:gg),(mod-1)/(len+len));for(int i=0;i<n;i+=len+len){int wk=1;for(int j=0;j<len;j++,wk=wk*w1%mod){int x=a[i+j],y=wk*a[i+j+len]%mod;a[i+j]=(x+y)%mod;a[i+j+len]=(x-y+mod)%mod;}}}if(t==-1){for(int i=0;i<n;i++){a[i]=a[i]*ksm(n,mod-2)%mod;}}
}
int init(int m){int n=1;while(n<m)n<<=1;for(int i=0;i<n;i++){rev[i]=(rev[i>>1]>>1);if(i&1)rev[i]|=(n>>1);}return n;
}
poly operator*(poly a,poly b){int n=a.size()+b.size()-1;int m=init(n);a.resize(m);b.resize(m);ntt(a,m,1);ntt(b,m,1);for(int i=0;i<m;i++){a[i]=a[i]*b[i]%mod;}ntt(a,m,-1);return a;
}
int bm(poly p,poly q,int n){while(n){poly qq=q;for(int i=1;i<q.size();i+=2){qq[i]=mod-q[i];}p=p*qq;q=q*qq;int i=(n&1);while(i<p.size()){p[i>>1]=p[i];i+=2;}p.resize(i>>1);i=0;while(i<q.size()){q[i>>1]=q[i];i+=2;}q.resize(i>>1);n>>=1;}if(!p.size())return 0;return p[0]*ksm(q[0],mod-2)%mod;
}
int f[N],a[N];
void solve(int cs){if(!cs)return;cin>>n>>k;for(int i=1;i<=k;i++){cin>>f[i];f[i]=(f[i]%mod+mod)%mod;}for(int i=0;i<k;i++){cin>>a[i];a[i]=(a[i]%mod+mod)%mod;}poly p,q,r;q.resize(k+1);q[0]=1;for(int i=1;i<=k;i++){q[i]=mod-f[i];}r.resize(k);for(int i=0;i<k;i++){r[i]=a[i];}p=q*r;p.resize(k);cout<<bm(p,q,n)<<'\n';
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// cin>>Tc;// init();for(int cs=1;cs<=Tc;cs++){solve(cs);}// cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';// cerr<<(&st-&ed)/1048576.0<<'\n';return 0;
}