多项式与生成函数

约定

[x^i]是取系数算子,后面紧跟一个多项式表示对这个多项式取系数.

$$[x^m]f(x)$$

普通生成函数 OGF

$$F(x)=\sum_{n}^{\infty}a_nx^n$$

指数生成函数 EGF

$$F(x)=\sum_{n}^{\infty}a_n\frac{x^n}{n!}$$

指数生成函数在卷积的时候比ogf多了一个组合数项.

相关科技

前缀和,差分

前缀和可以对函数乘上:

$$1/(1-x)$$

差分是前缀和的逆运算,乘上

$$(1-x)$$

多项式即可.

求单项远系数

给你一个生成函数f(x),求[x^i]f(x)(也就是求第i项的系数,i量级为1e18)

OGF例题

1. 分治FFT: 给定序列 $g_n$ 求 $f_n$ ,其中 $f_n=\sum_{j=1}^if_{i-j}g_{j}$ ,边界 $g_0=0,f_0=1$ ,对 $998244353$ 取模.

   设生成函数 $f(x)=\sum_{i=0}^{\infty}f[i]x^i,g(x)=\sum_{i=0}^{\infty}g[i]x^i,g[0]=0$
   然后使用生成函数卷积:

   $$f(x)*g(x)=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}f[i]\times g[j]x^{i+j}$$

   令 $k=i+j$ ,

   $$f(x)*g(x)=\sum_{k=0}^{\infty}\left(\sum_{j=0}^kf[k-j]g[j]\right)x^k$$

   当 $k<0$ 时 $\sum_{j=0}^kf[k-j]g[j]=f[k]$ 就是个普通卷积.
   当 $k=0$ 时 $\sum_{j=0}^kf[k-j]g[j]=0(g[0]=0)$ 于是和 $f(x)$ 对比一下发现差了个常数项,于是我们有

   $$\boxed{f(x)*g(x)+f[0]=f(x)}$$

   于是有

   $$\boxed{f(x)=\frac{f[0]}{1-g(x)}}$$

   使用多项式求逆即可解决.

2. Bostan-Mori: abc436g,给一个限制数组A,统计有多少个x数组满足Ax<=M,其中|A|<=100,a_i<=100,M<=1e18
   考虑无限背包问题的生成函数:

   $$1+x^{a_i}+x^{2a_i}+...=\frac{1}{1-x^{a_i}}$$

   多个生成函数直接乘起来即可,最后乘上前缀和算子,套用Bostan-Mori算法求出第M项.
   重点关注如何直接对多项式进行操作:类似背包的方法.

   poly makeQ(const vector<int>&A){
       int S=0;
       for(int a:A){
           S+=a;
       }//计算数组大小,无限背包可以拿很多,所以是sum不是lcm
       poly dp(S+1,0);
       dp[0]=1;
       for(int a:A){
           for(int s=S;s>=a;s--){
               dp[s]=(dp[s]-dp[s-a]+MOD)%MOD;
           }//分母Q是(1-x^{a_i})的卷积
       }
       poly Q(S+2,0);
       Q[0]=dp[0];
       for(int s=1;s<=S;s++){
           Q[s]=(dp[s]-dp[s-1]+MOD)%MOD;
       }//前缀和的倒数是差分.
       Q[S+1]=(MOD-dp[S])%MOD;
       while(!Q.empty()&&Q.back()==0){
           Q.pop_back();
       }//删除高位0
       return Q;
   }

EGF例题

1. 洛谷p5339
   S(a,b,c,d,n)的组合意义就是在四种颜色里面(有个数限制)取一些来涂色。

   这个是EGF经典问题,考虑构造 $R_k​(x)=∑_{i=0}k​ \frac{x^i}{i!}​$ ,就是k个同种颜色的EGF。

   EGF卷积的意义就是随意插入混合,那么我们把四个R卷起来之后取第n项就可以得到答案了。