重新改了一下板子 抄起来比较短
#include <bits/stdc++.h> using namespace std; #define rep(i,h,t) for (int i=h;i<=t;i++) #define dep(i,t,h) for (int i=t;i>=h;i--) #define ll long long #define IL inline const int mo=998244353; const int G=3; const int N=4e5; const int mxl=(1<<18); struct NTT{ int n,m,wn[N],a[N],b[N],C[N],D[N],inv[N]; int fsp(int x,int y) {int ans;for (ans=1;y;y>>=1,x=1ll*x*x%mo) if (y&1) ans=1ll*ans*x%mo; return ans;} void pre(){ inv[0]=inv[1]=1; rep(i,2,N-1) inv[i]=(1ll*inv[mo%i]*(mo-(mo/i)))%mo; int x=fsp(G,(mo-1)/mxl); wn[mxl>>1]=1; rep(i,(mxl>>1)+1,mxl-1) wn[i]=1ll*wn[i-1]*x%mo; dep(i,(mxl>>1)-1,1) wn[i]=wn[i<<1]; } inline int add(int x,int y) {return x+y>=mo?x+y-mo:x+y;} void clear() { rep(i,0,n) a[i]=b[i]=0; } void ntt(int *a,int f) { if (f>0){ for (int k=n>>1;k;k>>=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++){ int x=a[i+j],y=a[i+j+k]; a[i+j+k]=1ll*(x-y+mo)*wn[k+j]%mo; a[i+j]=add(x,y); } } else{ for (int k=1;k<n;k<<=1) for (int i=0;i<n;i+=(k<<1)) for (int j=0;j<k;j++){ int x=a[i+j],y=1ll*a[i+j+k]*wn[k+j]%mo; a[i+j+k]=add(x,mo-y); a[i+j]=add(x,y); } for (int i=0,inv=mo-(mo-1)/n;i<n;i++) a[i]=1ll*a[i]*inv%mo; reverse(a+1,a+n); } } IL void js(int *A,int *B,int len) { for (n=1;n<len;n*=2); for (int i=0;i<len;i++) a[i]=(A[i]%mo+mo)%mo,b[i]=(B[i]%mo+mo)%mo; ntt(a,1); ntt(b,1); for (int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%mo; ntt(a,-1); for (int i=0;i<len;i++) B[i]=a[i]; clear(); } IL void js(int *A,int len) { for (n=1;n<len;n*=2); ntt(a,1); ntt(b,1); for (int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%mo; ntt(a,-1); for (int i=0;i<len;i++) A[i]=a[i]; clear(); } IL void getcj(int *A,int *B,int len) { for (n=1;n<2*len;n*=2); for (int i=0;i<len;i++) a[i]=(A[i]%mo+mo)%mo,b[i]=(B[i]%mo+mo)%mo; ntt(a,1); ntt(b,1); for (int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%mo; ntt(a,-1); for (int i=0;i<len;i++) B[i]=a[i]; clear(); } IL void getinv(int *A,int *B,int len) { if (len==1) {B[0]=fsp(A[0],mo-2); return;} getinv(A,B,(len+1)>>1); for (n=1;n<=len*2;n*=2); for (int i=0;i<len;i++) a[i]=(A[i]%mo+mo)%mo,b[i]=(B[i]%mo+mo)%mo; ntt(a,1); ntt(b,1); for (int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%mo*b[i]%mo; ntt(a,-1); for (int i=0;i<len;i++) B[i]=((2*B[i]-a[i])%mo+mo)%mo; clear(); } IL void getsqrt(int *A,int *B,int len) { int inv2=fsp(2,mo-2); if (len==1) { B[0]=sqrt(A[0]); return;} getsqrt(A,B,(len+1)>>1); int C[N]; getinv(B,C,len); getcj(A,C,len); for (int i=0;i<n;i++) B[i]=1ll*(C[i]+B[i])%mo*inv2%mo; } IL void getDao(int *a,int *b,int len) { for (int i=1;i<len;i++) b[i-1]=1ll*i*a[i]%mo; b[len-1]=0; } IL void getjf(int *a,int *b,int len) { for (int i=0;i<=len;i++) b[i+1]=1ll*a[i]*inv[i+1]%mo; b[0]=0; } IL void getln(int *A,int *B,int len) { getDao(A,C,len); getinv(A,D,len); getcj(C,D,len); getjf(D,B,len); rep(i,0,len+1) C[i]=0,D[i]=0; } IL void getexp(int *A,int *B,int len) { if (len==1) {B[0]=1; return;} getexp(A,B,(len+1)>>1); int C[N]; getln(B,C,len); for(int i=0;i<len;i++) C[i]=((-C[i]+A[i])%mo+mo)%mo; C[0]=(C[0]+1)%mo; getcj(C,B,len); } }F; int now[N],f[N],g[N]; void solve(int h,int t) { if (h>=t) return; int mid=(h+t)/2; solve(h,mid); rep(i,h,mid) F.a[i-h]=f[i]; rep(i,1,t-h) F.b[i]=g[i]; F.js(now,(mid-h+1)+(t-h+1)); rep(i,mid+1,t) f[i]=(f[i]+now[i-h])%mo; solve(mid+1,t); } int tmpa[N],tmpb[N]; vector<int> operator *(const vector<int> &t1,const vector<int> &t2) { int n1=t1.size(),n2=t2.size(); rep(i,0,n1-1) tmpa[i]=t1[i]; rep(i,0,n2-1) tmpb[i]=t2[i]; F.js(tmpa,tmpb,n1+n2-1); vector<int> c; rep(i,0,n1+n2-2) c.push_back(tmpb[i]); rep(i,0,n1+n2) tmpa[i]=tmpb[i]=0; return c; } void operator += (vector<int> &a,const vector<int> &b){ if (b.size()>a.size()) a.resize(b.size()); for (int i=0,si=b.size();i<si;i++) a[i]=(a[i]+b[i])%mo; } struct re{ vector<int> a[2][2]; }M[N]; #define mid ((h+t)/2) re solve1(int h,int t) { if (h==t) return M[h]; re z; re x=solve1(h,mid),y=solve1(mid+1,t); rep(i,0,1) rep(j,0,1) rep(k,0,1) { z.a[i][k]+=x.a[i][j]*y.a[j][k]; } return z; } int a[N],b[N]; vector<int> ve[N]; #define vii vector<int> vii solve2(int h,int t) { if (h==t) return ve[h]; return solve2(h,mid)*solve2(mid+1,t); } int main() { F.pre(); return 0; } // /* 3 2 1 2 2 1 2 2 1 2 */
原文地址:http://www.cnblogs.com/yinwuxiao/p/16826564.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性