[关闭]
@jason-fan 2021-04-06T10:38:06.000000Z 字数 6189 阅读 146

CODE

  1. #pragma GCC optimize(2)
  2. #pragma GCC optimize(3)
  3. #pragma GCC optimize(3,"Ofast","inline")
  5. #include <algorithm>
  6. #include <iostream>
  7. #include <cstring>
  8. #include <vector>
  9. #include <cstdio>
  10. #include <cmath>
  11. #include "../debuger.h"
  12. using namespace std;
  13. template<typename _Tp>
  14. inline void red(_Tp &x) {
  15.     x=0;bool fg=0;char ch=getchar();
  16.     while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
  17.     while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(_Tp)(ch^48),ch=getchar();
  18.     if(fg) x=-x;
  19. }
  20. typedef long long ll;
  22. /*-------------------------------BEGIN POLY FAMILY BUCKET---------------------------------------*/
  24. #define clr(f,n) memset(f,0,sizeof(long long)*(n))
  25. #define cpy(f,g,n) memcpy(f,g,sizeof(long long)*(n))
  26. #define Outarr(x,n) cerr<<#x<<" : "; for(int i=0;i<n;++i) cerr<<x[i]<<" ";cout<<endl;
  27. #define outarr(x,n) for(int i=0;i<n;++i) printf("%lld%c",x[i],(i==n-1)?'\n':' ');
  28. #define MOD(x) ((x)<mod?(x):((x)%mod))
  29. namespace poly {
  30.     const int mod = 998244353;
  31.     const int N = (1<<19);
  32.     const int _G = 3;
  33.     const int _iG = 332748118;
  34.     const int inv2 = 499122177;
  36.     ll fpow(ll a,ll b,ll p) {
  37.         ll r=1;
  38.         for(;b;a=a*a%p,b>>=1) if(b&1) r=r*a%p;
  39.         return r;
  40.     }
  42.     int rev[N],rev_n;
  43.     void prerev(int n) {
  44.         if(n==rev_n) return;
  45.         rev_n=n;
  46.         for(int i=0;i<n;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
  47.     }
  48.     // NTT : fg=1 DFT fg=-1 IDFT
  49.     template<typename IT>  
  50.     void NTT(IT f,int n,int fg) {
  51.         prerev(n);
  52.         for(int i=0;i<n;++i) if(i<rev[i]) swap(f[i],f[rev[i]]);
  53.         for(int h=2;h<=n;h<<=1) {
  54.             ll Dt=fpow((fg==1)?_G:_iG,(mod-1)/h,mod),w;
  55.             int len=h>>1;
  56.             for(int j=0;j<n;j+=h) {
  57.                 w=1;
  58.                 for(int k=j;k<j+len;++k) {
  59.                     ll tmp=MOD(f[k+len]*w);
  60.                     f[k+len]=f[k]-tmp; (f[k+len]<0)&&(f[k+len]+=mod); 
  61.                     f[k]=f[k]+tmp; (f[k]>=mod)&&(f[k]-=mod); 
  62.                     w=MOD(w*Dt);
  63.                 }
  64.             }
  65.         }
  66.         if(fg==-1) {
  67.             ll invn=fpow(n,mod-2,mod);
  68.             for(int i=0;i<n;++i) f[i]=MOD(f[i]*invn);
  69.         }
  70.     }
  71.     // f(x) = f*g(x) n = def f ; m = def g ; len = 最终长度(保留几位) 
  72.     void p_mul(ll f[],ll g[],int n,int m,int len) {
  73.         static ll a[N],b[N];
  74.         int nn=1<<(int)ceil(log2(n+m-1));
  75.         clr(a,nn); clr(b,nn); cpy(a,f,n); cpy(b,g,m);
  76.         NTT(a,nn,1); NTT(b,nn,1);
  77.         for(int i=0;i<nn;++i) a[i]=MOD(a[i]*b[i]); 
  78.         NTT(a,nn,-1);
  79.         for(int i=0;i<len;++i) f[i]=a[i];
  80.     }
  81.     // f(x) = g^-1(x)  f(x) 为 g(x) 模 x^n 意义下的逆
  82.     void p_inv(ll g[],int n,ll f[]) {
  83.         static ll sav[N];
  84.         int nn=1<<(int)ceil(log2(n));
  85.         clr(f,n*2);
  86.         f[0]=fpow(g[0],mod-2,mod);
  87.         for(int h=2;h<=nn;h<<=1) {
  88.             cpy(sav,g,h); clr(sav+h,h);
  89.             NTT(sav,h<<1,1); NTT(f,h<<1,1);
  90.             for(int i=0;i<(h<<1);++i) {
  91.                 f[i]=f[i]*(2ll-f[i]*sav[i]%mod+mod)%mod;
  92.             } 
  93.             NTT(f,h<<1,-1); clr(f+h,h);
  94.         }
  95.         clr(f+n,nn*2-n);
  96.     }
  97.     // f^2(x) = g(x)  f(x) 为 g(x) 模 x^n 意义下的开方
  98.     void p_sqrt(ll g[],int n,ll f[]) {
  99.         static ll sav[N],r[N];
  100.         int nn=1<<(int)ceil(log2(n));
  101.         clr(f,n*2); f[0]=1; // g[0] should be 1 otherwise 
  102.         for(int h=2;h<=nn;h<<=1) {
  103.             cpy(sav,g,h); clr(sav+h,h); p_inv(f,h,r);
  104.             NTT(sav,h<<1,1); NTT(r,h<<1,1);
  105.             for(int i=0;i<(h<<1);++i) sav[i]=MOD(sav[i]*r[i]);
  106.             NTT(sav,h<<1,-1);
  107.             for(int i=0;i<h;++i) f[i]=MOD((f[i]+sav[i])*inv2);
  108.             clr(f+h,h);
  109.         }
  110.         clr(f+n,nn*2-n);
  111.     }
  112.     // f(x) = g(x) * q(x) + r(x) : q(x) 为商 r(x) 为余数
  113.     void p_div(ll f[],ll g[],int n,int m,ll q[],ll r[]) {
  114.         static ll sav1[N],sav2[N];
  115.         int nn; for(nn=1;nn<n-m+1;nn<<=1);
  116.         clr(sav1,nn); clr(sav2,nn); cpy(sav1,f,n); cpy(sav2,g,m);
  117.         reverse(sav1,sav1+n); reverse(sav2,sav2+m); 
  118.         p_inv(sav2,n-m+1,q); p_mul(q,sav1,n-m+1,n,n-m+1);
  119.         reverse(q,q+n-m+1); cpy(r,g,m);
  120.         p_mul(r,q,m,n-m+1,m-1);
  121.         for(int i=0;i<m-1;++i) r[i]=MOD(f[i]-r[i]+mod); 
  122.     }
  123.     // 预处理乘法逆元
  124.     ll inv[N],fac[N],ifac[N];
  125.     void Initinv(int n) {
  126.         inv[0]=inv[1]=1;
  127.         fac[0]=fac[1]=ifac[0]=ifac[1]=1;
  128.         for(int i=2;i<n;++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
  129.         for(int i=2;i<n;++i) fac[i]=fac[i-1]*i%mod;
  130.         for(int i=2;i<n;++i) ifac[i]=ifac[i-1]*inv[i]%mod;
  131.     }
  132.     // 对 f(x) 进行积分  Initinv() first 
  133.     void p_int(ll f[],int n) {
  134.         for(int i=n-1;i;--i) f[i]=MOD(f[i-1]*inv[i]);
  135.         f[0]=0;
  136.     }
  137.     // 对 f(x) 进行求导 
  138.     void p_der(ll f[],int n) {
  139.         for(int i=1;i<n;++i) f[i-1]=MOD(f[i]*i);
  140.         f[n-1]=0;
  141.     }
  142.     //  f(x) <- ln f(x)  f[0] should be 1
  143.     void p_ln(ll f[],int n) {
  144.         static ll g[N];
  145.         p_inv(f,n,g); p_der(f,n);
  146.         p_mul(f,g,n,n,n+n); 
  147.         p_int(f,n);
  148.     }
  150.     // f(x) <- exp f(x) (倍增版) f[0] should be 0
  151.     void p_exp(ll f[],int n) { 
  152.         static ll g[N],sav[N];
  153.         clr(g,n*2); clr(sav,n*2); g[0]=1;
  154.         for(int h=2;h<=n;h<<=1) {
  155.             cpy(sav,g,h); p_ln(sav,h);
  156.             for(int i=0;i<h;++i) sav[i]=MOD(f[i]-sav[i]+mod);
  157.             sav[0]=MOD(sav[0]+1);
  158.             p_mul(g,sav,h,h,h);
  159.         }
  160.         cpy(f,g,n);
  161.     }
  163.     /* 
  164.     void _p_exp(ll f[],ll g[],int l,int r) {
  165.         static ll A[N],B[N];
  166.         if(r-l==1) {if(l>0) f[l]=MOD(f[l]*fpow(l,mod-2,mod));return ;}
  167.         int mid=(l+r)>>1,len=mid-l;
  168.         _p_exp(f,g,l,mid);
  169.         cpy(A,f+l,len); clr(A+len,len); cpy(B,g,len<<1); 
  170.         p_mul(A,B,len<<1,len<<1,len<<1);
  171.         for(int i=mid;i<r;++i) f[i]=MOD(f[i]+A[i-l]);
  172.         _p_exp(f,g,mid,r);
  173.     }
  174.     // f(x) <- exp f(x) (分治 FFT 版) f[0] should be 0
  175.     void p_exp(ll f[],int n) { 
  176.         static ll g[N];
  177.         cpy(g,f,n); clr(f,n); f[0]=1;
  178.         for(int i=0;i<n;++i) g[i]=MOD(g[i]*i);
  179.         _p_exp(f,g,0,n);
  180.     }
  181.     */
  183.     // f(x) <- f^k(x)  f(x) 模 x^n 意义下的 k 次
  184.     void p_pow(ll f[],int n,ll k) {
  185.         p_ln(f,n);
  186.         for(int i=0;i<n;++i) f[i]=MOD(f[i]*k);
  187.         p_exp(f,n);
  188.     }
  190.     // 分治FFT [l,r)   F[n] = sum(0<i<=n) F[n-i]G[i] 
  191.     void DCFFT(ll f[],ll g[],int l,int r) { 
  192.         static ll A[N],B[N];
  193.         if(r-l==1) return ;
  194.         int mid=(l+r)>>1,len=mid-l;
  195.         DCFFT(f,g,l,mid);
  196.         cpy(A,f+l,len); clr(A+len,len); cpy(B,g,len<<1); 
  197.         p_mul(A,B,len<<1,len<<1,len<<1);
  198.         for(int i=mid;i<r;++i) f[i]=MOD(f[i]+A[i-l]);
  199.         DCFFT(f,g,mid,r);
  200.     }
  201. }
  202. using poly::p_ln;
  203. using poly::p_exp;
  204. using poly::p_inv;
  205. using poly::p_mul;
  206. using poly::NTT;
  207. using poly::ifac;
  208. using poly::fac;
  209. using poly::inv;
  210. using poly::mod;
  212. /*------------------------------- END POLY FAMILY BUCKET ---------------------------------------*/
  215. const int N = (1<<19);
  217. int n,m,nn;
  218. ll a[N],G[N],f[N],h[N];
  219. vector<ll> F[N<<2][2];
  221. #define ls (x<<1)
  222. #define rs (x<<1|1)
  223. void solve(int l=1,int r=n,int x=1) {
  224.     if(l==r) {
  225.         F[x][0].resize(2,0);
  226.         F[x][1].resize(2,0);
  227.         F[x][0][0]=1;
  228.         F[x][1][0]=1;
  229.         F[x][1][1]=mod-a[l];
  230.         return ;
  231.     }
  232.     int mid=(l+r)>>1;
  233.     solve(l,mid,ls);solve(mid+1,r,rs);
  234.     int n=F[ls][1].size()+F[rs][1].size()-1;
  235.     int nn=1<<(int)ceil(log2(n));
  236.     F[ls][0].resize(nn,0);F[ls][1].resize(nn,0);
  237.     F[rs][0].resize(nn,0);F[rs][1].resize(nn,0);
  238.     F[x][0].resize(nn,0);F[x][1].resize(nn,0);
  239.     NTT(F[ls][0].begin(),nn,1);
  240.     NTT(F[rs][0].begin(),nn,1);
  241.     NTT(F[ls][1].begin(),nn,1);
  242.     NTT(F[rs][1].begin(),nn,1);
  243.     for(int i=0;i<nn;++i)
  244.         F[x][1][i]=MOD(F[ls][1][i]*F[rs][1][i]);
  245.     for(int i=0;i<nn;++i) 
  246.         F[x][0][i]=(F[ls][1][i]*F[rs][0][i]+F[ls][0][i]*F[rs][1][i])%mod;
  247.     NTT(F[x][0].begin(),nn,-1);
  248.     NTT(F[x][1].begin(),nn,-1);
  249.     F[x][0].resize(n,0);
  250.     F[x][1].resize(n,1);
  251. }
  253. int main() {
  254.     red(n);red(m);
  255.     nn=1<<(int)ceil(log2(m+1));
  256.     poly::Initinv(1<<19);
  257.     for(int i=0;i<nn;++i) G[i]=ifac[i+1];
  258.     p_ln(G,nn);
  259.     for(int i=1;i<=n;++i) {
  260.         red(a[i]);a[i]%=mod;
  261.     }
  262.     solve();
  263.     seeln(F[1][0]); seeln(F[1][1]); 
  264.     for(int i=0;i<nn;++i) {
  265.         if(i>=F[1][1].size()) break;
  266.         f[i]=F[1][1][i];
  267.     }
  268.     p_inv(f,nn,h);
  269.     clr(f,nn);
  270.     for(int i=0;i<nn;++i) {
  271.         if(i>=F[1][0].size()) break;
  272.         f[i]=F[1][0][i];
  273.     }
  274.     p_mul(f,h,nn,nn,nn);
  276.     outarr(f,nn);
  279.     for(int i=0;i<nn;++i) {
  280.         G[i]=G[i]*f[i]%mod;
  281.     }
  282.     p_exp(G,nn);
  283.     for(int i=1;i<=m;++i) {
  284.         ll ans=fac[i]*G[i]%mod;
  285.         printf("%lld ",ans);
  286.     }
  287.     puts("");
  288.     return 0;
  289. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注