下降幂多项式乘法小结-白红宇

下降幂多项式乘法小结

阅读量：2306 次

发布时间：2019-05-09

本文共 2017 字，大约阅读时间需要 6 分钟。

正题

考虑求出下降幂多项式 $F (x)$ 的点值生成函数，即 $F'(x)=\sum_{i=0} \dfrac {F(i)} {i!} x^i$ 。

设 $F_i$ 表示 $F (x)$ 中 $x^i$ 的系数，那么有 $F(x)=\sum_{i=0} F_i x^{\underline i}$

推一推柿子：

F'(x)=\sum_{i=0} \frac {F(i)} {i!} x^i=\sum_{i=0} \frac {x^i} {i!} \sum_{j=0} F_j i^{\underline j}=\sum_{j=0} F_j \sum_{i=0} \frac {x^i} {i!} i^{\underline j}

发现有一个性质：

\sum_{i=0} \frac {i^{\underline j}} {i!} x^i=\sum_{i=0} \frac 1 {(i-j)!}x^i=x^j\sum_{i=0} \frac {x^i} {i!}=x^j e^x

带回去得到：

F'(x)=\sum_{j=0} F_jx^je^x=e^x\sum_{j=0} F_jx^j

也就是说，让 $F (x)$ 卷上 $e^x$ 就得到 $F^{'} (x)$ 了！

得到了 $F^{'} (x)$ 和 $G^{'} (x)$ 之后，就可以做点值乘法，然后逆运算，即乘以 $e^{-x}$ 就是答案。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;#define maxn 600010#define mod 998244353#define bin(x) (1<<(x))int n,m,F[maxn],G[maxn];int ksm(int x,int y){
   int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}int inv[maxn],w[maxn];void prep(int lg){
   int N=bin(lg);	inv[1]=1;for(int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;	for(int i=1,wn;i
       
        <<=1){
   		w[i]=1;wn=ksm(3,(mod-1)/(i<<1));		for(int j=1;j
        
         >1]>>1)|((i&1)<<(lg-1));}int add(int x){ return x>=mod?x-mod:x;}int dec(int x){ return x<0?x+mod:x;}void ntt(int *f,int lg,int type=0){ limit=bin(lg);if(type)reverse(f+1,f+limit); for(int i=1;i
         
          
           =1;i--)inv_fac[i]=1ll*inv_fac[i+1]*(i+1)%mod;}int EX[maxn],E_X[maxn];void NTT_Des(int *f,int *g,int ln){ int lg=ceil(log2(ln<<1)); #define work_EX() memset(EX,0,4<