多项式exp求调
查看原帖
多项式exp求调
752441
CuFeO4楼主2025/2/7 21:24

多项式 ln 能过板子,static 数组已清空,样例只有最后两个数有错。

在 namespace 最下面。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
  auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
  auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
namespace PolyBasedNTT{
using std::memset;using std::memcpy;using std::swap;using std::reverse;
#define N LEN
  const int Mod = 998244353,G = 3,Gi = 332748118;
  const int LEN = 4e6 + 10;
  int lastnnn = 0,lastlim = 0,initinvn = 0,_to[N],_inv[N];
  int qpow(int a,int b,int Mod = Mod){
    int res = 1;
    for(;b;b >>= 1,a = 1ll*a*a%Mod)
      if(b&1) res = 1ll*res*a%Mod;
    return res;
  }
  int invi(int a){return qpow(a,Mod-2,Mod);}
  template<class T>
  T FMod(const T x){return x >= Mod?x - Mod:x;}
  void bfconvolution(int *a,int *b,int lena,int lenb){
    static int w[N];
    for(int i = 0;i < lena; ++i) for(int j = 0;j < lenb; ++j)
      w[i+j] = FMod(w[i+j]+1ll*a[i]*b[j]%Mod);
    copy(w,w+lena+lenb,a);
    fill(w,w+lena+lenb,0);
  }
  int _prepare(int n){
    if(lastnnn == n) return lastlim;
    lastnnn = n;
    uint lim = 1,ct = -1;while(lim <= n) lim <<= 1,ct++;
    for(int i = 0;i < lim; ++i) _to[i] = (_to[i>>1]>>1)|((i&1)<<ct);
    return (lastlim = lim);
  }
  void mult(int *f,int *g,int len){for(int i = 0;i < len; ++i) f[i] = 1ll*f[i]*g[i]%Mod;}
  void clear(int *f,int len,int val = 0){memset(f,val,4*len);}
  void cpy(int *f,int *g,int len){memcpy(f,g,4*len);}
  void NTT(int *a,int n,bool type = true){
    n = _prepare(n);
    for(int i = 0;i < n; ++i) if(i < _to[i]) swap(a[i],a[_to[i]]);
    for(int mid = 1;mid < n;mid <<= 1){
      int W = qpow(type?G:Gi,(Mod-1)/(mid<<1));
      for(int Res = mid<<1,j = 0;j < n;j += Res){
        int w = 1;
        for(int k = 0;k < mid; ++k,w = 1ll*w*W%Mod){
          int x = a[j+k],y = 1ll*w*a[j+k+mid]%Mod;
          a[j+k] = FMod(x+y);
          a[j+k+mid] = FMod(x-y+Mod);
        }
      }
    }
  }
  void convolution(int *a,int *b,int n,int m){
    int len = n + m,llen = invi(_prepare(len)),Len = _prepare(len);
    static int sav[N];
    clear(sav,len);cpy(sav,b,len);
    NTT(a,len);if(a != b) NTT(b,len);
    for(int i = 0;i < Len; ++i) a[i] = 1ll*a[i]*b[i]%Mod;
    NTT(a,len,false);
    for(int i = 0;i < len; ++i) a[i] = 1ll*a[i]*llen%Mod;
    fill(a+len,a+Len,0);cpy(b,sav,len);
  }
  void invp(int *b,int *a,int n){
    if(n == 1) return b[0] = invi(a[0]),void();
    invp(b,a,(n+1)>>1);
    static int c[N];
    int emm = 2*n-1,len = _prepare(emm);
    cpy(c,a,n);
    clear(c+n,len-n+1);
    NTT(c,emm);NTT(b,emm);
    for(int i = 0;i < len; ++i) b[i] = FMod(2ll-1ll*b[i]*c[i]%Mod+Mod)*b[i]%Mod;
    NTT(b,emm,0);int invn = invi(len);
    for(int i = 0;i < n; ++i) b[i] = 1ll*b[i]*invn%Mod;
    clear(b+n,len-n+1);
  }
  void invp(int *a,int n){
    static int b[N];invp(b,a,n);
    cpy(a,b,n+1);
    clear(b,lastlim);
  }
  void sqrtp(int *a,int n){
    static int b1[N],b2[N],b3[N];
    int m = n + 1;n = 1;while(n <= m) n <<= 1;
    b1[0] = 1;
    for(int len = 2;len <= n;len <<= 1){
      for(int i = 0;i < (len>>1); ++i) b2[i] = b1[i];
      for(int i = 0;i < len; ++i) b3[i] = a[i];
      invp(b2,len);
      convolution(b3,b2,len,len);
      for(int i = 0;i < len; ++i) b1[i] = FMod(b1[i]+b3[i])*499122177ll%Mod;
      clear(b2,lastlim);clear(b3,lastlim);clear(b1+len,lastlim-len);
    }
    cpy(a,b1,m);clear(b1,n+n);clear(b2,n+n);clear(b3,n+n);
  }
  void rev(int *f,int len){reverse(f,f+len);}
  void modp(int *f,int *g,int n,int m){
    static int q[N],t[N];
    int L = n-m+1;
    rev(g,m);cpy(q,g,L);rev(g,m);
    rev(f,n);cpy(t,f,L);rev(f,n);
    invp(q,L);convolution(q,t,L,L);rev(q,L);
    fill(q+L,q+lastlim,0);
    convolution(g,q,n,n);
    for(int i = 0;i < m-1; ++i) g[i] = FMod(f[i]-g[i]+Mod);
    cpy(f,q,L);
    clear(f+L,n-L);
    clear(q,lastlim);clear(t,lastlim);
  }
  void Diff(int *f,int n){
    for(int i = 0;i < n - 1; ++i) f[i] = 1ll*(i+1)*f[i+1]%Mod;
    f[n-1] = 0;
  }
  void Init(int *inv,int n){
    if(initinvn >= n) return;
    if(initinvn == 0){
      inv[1] = 1;
      for(int i = 2;i <= n; ++i) inv[i] = 1ll*inv[Mod%i]*(Mod-Mod/i)%Mod;
      initinvn = n;
    }
    else{
      for(int i = initinvn + 1;i <= n; ++i) inv[i] = 1ll*inv[Mod%i]*(Mod-Mod/i)%Mod;
      initinvn = n;
    }
  }
  void integral(int *f,int n){
    Init(_inv,n);
    for(int i = n; i; --i) f[i] = 1ll*f[i-1]*_inv[i]%Mod;
    f[0] = 0;
  }
  void ln(int *f,int n){
    static int g[N];
    cpy(g,f,n);
    invp(g,n);
    int LL = lastlim;
    Diff(f,n);
    convolution(f,g,n,n);
    integral(f,n-1);
    memset(g,0,sizeof g);
    clear(g,lastlim);
  }
  void exp(int *f,int m){
    static int s[N],s2[N],res[N];
    int n = 1;while(n < m) n <<= 1;
    s2[0] = 1;
    for(int len = 2;len <= n;len <<= 1){
      cpy(s,s2,len>>1);ln(s,len);
      for(int i = 0;i < len; ++i) s[i] = FMod(f[i]-s[i]+Mod);
      s[0] = FMod(s[0] + 1);
      convolution(s2,s,len,len);
    }
    cpy(f,s2,m);clear(s,n);clear(s2,n);
  }
#undef N
}using namespace PolyBasedNTT;
const int N = 4e5 + 10;
int n,a[N];
signed main(){
  cin.tie(nullptr)->sync_with_stdio(false);
  cin>>n;
  for(int i = 0;i < n; ++i) cin>>a[i];
  exp(a,n);
  for(int i = 0;i < n; ++i) cout<<a[i]<<' ';cout<<'\n';
}
2025/2/7 21:24
加载中...