学习笔记·多项式专题（三）

在这一篇文章里，我们来谈一谈上升幂，下降幂多项式，斯特林数以及一些优美的结论。

前言

如果有什么比如说像链接有问题或者是别的问题，包括不懂的，请在下面发讨论。

下降幂多项式的定义

下降幂多项式（$\texttt{Falling Factorial Polynomial}$，也即$\texttt{FFP}$），也称下降阶乘幂多项式，是一类特殊的多项式。

首先，看一下下降幂单项式的递归定义：

$$x^{\underline n}=\begin{cases}1, & n=0\\x\times (x-1)^{\underline{n-1}}, & n\geq 1\end{cases}$$

所以说，$x^{\underline 0}=1$，那么$x^{\underline 1}$呢？

$$x^{\underline 1}=x\times (x-1)^{\underline 0}=x$$

那么有

$$x^{\underline 2}=x\times (x-1)^{\underline 1}=x(x-1)=x^2-x$$ $$x^{\underline 3}=x\times (x-1)^{\underline 2}=x(x-1)(x-2)=x^3-3x^2+2x$$

于是可以得出一个普遍的结论，就是

$$x^{\underline n}=x(x-1)\cdots(x-n+1)=\frac{x!}{(x-n)!}=n!C_x^n$$

$x^{\underline n}=n!C^n_x$这个公式很重要，因为$x^{\underline n}$与两类斯特林数有强关联。

那么，下降幂多项式，是由许多个下降幂单项式相加得来的，如

$$3x^{\underline 2}+2x^{\underline 1}+1=3x(x-1)+2x+1=3x^2-x+1$$

普通多项式转下降幂多项式

Luogu P5383

首先看一个简单的结论：

$$n^m=\sum\limits_{i=0}^{m}i!S^i_mC^i_n$$

其中$S$表示第二类斯特林数。

为什么呢？考虑等号两边的组合意义。

左边是$n$个球任意放$m$个盒子的答案，右边的话枚举非空盒子的数量，用组合数枚举一下，最后由于盒子不同，所以要乘个$i!$。

所以，把它拓展一下，得到一个跳跃性结论：

$$x^n=\sum\limits_{i=0}^{n}i!S^i_nC^i_x$$

这时，我们看到了$i!C_i^x$的形式，考虑把它转成下降幂多项式，那么就会有

$$x^n=\sum\limits_{i=0}^{n}S^i_nx^{\underline i}$$

于是我们就把普通单项式转换成了一个下降幂单项式。但如果拓展成普通多项式，结论又会是什么？

设$n$次多项式$F(x)$的系数数列为$f$，那么有

$$F(x)=\sum\limits_{i=0}^nf_ix^i$$

把结论用上去，有

$$F(x)=\sum\limits_{i=0}^nf_i\sum\limits_{j=0}^{i}S_i^jx^{\underline j}$$

这里有一个小$\texttt{trick}$，改变求和顺序！所以说

$$F(x)=\sum\limits_{j=0}^nx^{\underline j}\sum\limits_{i=j}^{n}S_i^jf_i$$

本来$i$的下界应该是$0$的，但是当$i<j$时$S_i^j=0$，所以可以将$i$的下界改成$j$。

这就是一个下降幂多项式的形式了，看来问题解决了！但是后面一长串和式该怎么求？

这里有一个小结论：（证明在下面，用心找可以找得到）

$$S^n_m=\sum\limits_{i=0}^n\frac{(-1)^{n-i}}{(n-i)!}\cdot\frac{i^m}{i!}$$

所以，把结论用上去啊。。。

$$\sum\limits_{i=j}^{n}S_i^jf_i=\sum\limits_{i=j}^{n}\sum\limits_{k=0}^{j}\frac{(-1)^{j-k}}{(j-k)!}\cdot\frac{f_ik^i}{k!}$$

改变求和顺序，有

$$\sum\limits_{i=j}^{n}S_i^jf_i=\sum\limits_{k=0}^{j}\frac{(-1)^{j-k}}{(j-k)!}\cdot\sum\limits_{i=j}^{n}\frac{f_ik^i}{k!}$$

这就是卷积的形式了，直接$\texttt{NTT}$就好啦qwq。但是求后面那个和式要多点求值。

接着就是神奇的上代码环节啦。。。（包括预处理）

inline void polyToFFP(ll fd,ll *f,ll *res)
{
    static ll pts[MAXN>>1],tmp[MAXN],tmp2[MAXN];
    for(register int i=0;i<fd;i++)
    {
    	pts[i]=i,tmp[i]=(i&1)?MOD-finv[i]:finv[i];
    }
    eval(fd,fd,f,pts,tmp2);
    for(register int i=0;i<fd;i++)
    {
    	tmp2[i]=(li)tmp2[i]*finv[i]%MOD,pts[i]=0;
    }
    ll cnt=1,limit=-1;
    while(cnt<(fd<<1))
    {
    	cnt<<=1,limit++;
    }
    for(register int i=0;i<cnt;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<limit);
    }
    NTT(tmp2,cnt,1),NTT(tmp,cnt,1);
    for(register int i=0;i<cnt;i++)
    {
        res[i]=(li)tmp[i]*tmp2[i]%MOD,tmp[i]=tmp2[i]=0;	
    }
    NTT(res,cnt,-1);
}

下降幂多项式乘法

Luogu P5394

首先，拿题目的样例来解释一下：

$\quad(3x^{\underline 2}+2x^{\underline 1}+1)(4x^{\underline 3}+3x^{\underline 2}+2x^{\underline 1}+1)$
$=(3x^2-x+1)(4x^3-9x^2+7x+1)$
$=12x^5-30x^4+34x^3-12x^2+6x+1$
$=12x^{\underline 5}+89x^{\underline 4}+148^{\underline 3}+52x^{\underline 2}+8x^{\underline 1}+1$

难道要普通多项式与下降幂多项式的转换吗？题目难度告诉我们不要。但又怎么做呢？

考虑通过$\texttt{EGF}$将普通多项式与下降幂多项式建立联系，自然考虑下降幂单项式$x^{\underline n}$的$\texttt{EGF}$，设它为$g(x)$，那么有：

$$g(x)=\sum\limits_{i=n}^{\infty}\frac{i!}{(i-n)!i!}x^i$$

把$x^n$提出来并约分

$$g(x)=x^n\sum\limits_{i=n}^{\infty}\frac{1}{(i-n)!}x^{i-n}$$

改变求和符号的变量

$$g(x)=x^n\sum\limits_{i=0}^{\infty}\frac{x^i}{i!}$$

和式就是$e^x$的麦克劳林级数，所以

$$g(x)=x^ne^x$$

设$F(x)$为下降幂多项式$f(x)$点值的$\texttt{EGF}$，$G(x)$为下降幂多项式$f(x)$系数的$\texttt{EGF}$，$f$是$f(x)$的系数数组，因为

$$f(x)=\sum\limits_{i=0}^{n}f_ix^{\underline i}$$

所以

$$F(x)=\sum\limits_{i=0}^{n}f_ie^xx^i$$

把$e^x$提出来

$$F(x)=e^x\sum\limits_{i=0}^{n}f_ix^i$$ $$F(x)=e^xG(x)$$

所以说，下降幂多项式的点值和系数是可以互相转换的。只要得到两个下降幂多项式的点值，把对应点值乘起来再转系数就可以了，这些操作都可以通过简单的多项式乘法实现。

于是上一个令人身心愉悦的代码qwq（预处理跟上面的代码一模一样）

inline void FFPMul(ll fd,ll gd,ll *f,ll *g,ll *res)
{
    static ll tmp[MAXN],tmpf[MAXN],tmpg[MAXN];
    ll cnt=1,limit=-1;
    for(register int i=0;i<fd;i++)
    {
        tmpf[i]=f[i];
    }
    for(register int i=0;i<gd;i++)
    {
        tmpg[i]=g[i];
    }
    for(register int i=0;i<fd+gd-1;i++)
    {
        tmp[i]=finv[i];
    }
    while(cnt<(fd+gd<<1))
    {
        cnt<<=1,limit++;
    }
    for(register int i=0;i<cnt;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<limit);
    }
    NTT(tmpf,cnt,1),NTT(tmpg,cnt,1),NTT(tmp,cnt,1);
    for(register int i=0;i<cnt;i++)
    {
        
        tmpf[i]=(li)tmpf[i]*tmp[i]%MOD,tmpg[i]=(li)tmpg[i]*tmp[i]%MOD;
    }
    NTT(tmpf,cnt,-1),NTT(tmpg,cnt,-1);
    for(register int i=0;i<cnt;i++)
    {
        tmp[i]=i<fd+gd-1?(i&1?(MOD-finv[i]):finv[i]):0;
        tmpf[i]=i<fd+gd-1?(li)tmpf[i]*tmpg[i]%MOD*fact[i]%MOD:0;
    }
    NTT(tmpf,cnt,1),NTT(tmp,cnt,1);
    for(register int i=0;i<cnt;i++)
    {
        res[i]=(li)tmpf[i]*tmp[i]%MOD,tmpf[i]=tmpg[i]=tmp[i]=0;
    }
    NTT(res,cnt,-1);
}

第二类斯特林数·行

Luogu P5395

不知道第二类斯特林数的去看组合专题（大坑）。

还记得上面那个有关于第二类斯特林数的结论吗？

可是这又与这题有什么关系呢？

很明显，$m\leq n$，所以把和式上界改一下，为后续做准备

$$n^m=\sum\limits_{i=0}^{n}i!S^i_mC^i_n$$

然后再设$f(n)=n^m,g(i)=i!S^i_m$，那么有

$$f(n)=\sum\limits_{i=0}^{n}C^i_ng(i)$$

这是什么？二项式反演啊，所以反演一下

$$g(n)=\sum\limits_{i=0}^{n}(-1)^{n-i}C^i_nf(i)$$

再换回来

$$n!S^n_m=\sum\limits_{i=0}^n(-1)^{n-i}i^mC^i_n$$

把阶乘除过去，把组合数拆出来

$$S^n_m=\sum\limits_{i=0}^n\frac{1}{n!}\cdot\frac{n!}{i!(n-i)!}(-1)^{n-i}i^m$$

约个分

$$S^n_m=\sum\limits_{i=0}^n\frac{(-1)^{n-i}i^m}{i!(n-i)!}$$

然后再拆一下

$$S^n_m=\sum\limits_{i=0}^n\frac{(-1)^{n-i}}{(n-i)!}\cdot\frac{i^m}{i!}$$

很明显的卷积形式啊。。。$\texttt{NTT}$做就行啦qwq

时间复杂度$O(n\log n)$

代码呢？不见了。。。

第二类斯特林数·列

Luogu P5396

我们先从一个小结论入手（从维基百科蒯的）:

$$\sum\limits_{i=n}^{\infty}\frac{S_i^n}{i!}x^i=\frac{(e^x-1)^n}{n!}$$

证明留给读者做练习这掩盖不了我不会证的事实

这里主要讲讲求法。

很明显的把$e^x-1$拆开

$$e^x-1=\sum\limits_{i=1}^\infty\frac{x^n}{n!}$$

构造这样一个多项式，$n$次方之后对每一个系数乘上$n!$的逆元，再对于$x^i$的系数乘上$i!$就没了

时间复杂度$O(n\log n)$，代码无。

第一类斯特林数·列

先看一个恒等式

$$(x+1)^n=(x+1)^n$$

你可能会想，这样一个恒等式与斯特林数有啥关系嘛。且听我慢慢道来。

左边二项式展开，右边化成指数形式，有

$$\sum\limits_{i=0}^{n}C_n^ix^i=e^{n\ln (x+1)}$$

当$i>n$时，显然，$C_n^i=0$，所以左边改变求和上界，右边泰勒展开，有

$$\sum\limits_{i=0}^{\infty}C_n^ix^i=\sum\limits_{i=0}^{\infty}\frac{n^i\ln(x+1)^i}{i!}$$

把组合数拆成下降幂的形式

$$\sum\limits_{i=0}^{\infty}\frac{x^i}{i!} n^{\underline i}=\sum\limits_{i=0}^{\infty}\frac{n^i\ln(x+1)^i}{i!}$$

下降幂拆成第一类斯特林数

$$\sum\limits_{i=0}^{\infty}\frac{x^i}{i!} \sum\limits_{j=0}^{i}(-1)^{i-j}s_i^jn^i=\sum\limits_{i=0}^{\infty}\frac{n^i\ln(x+1)^i}{i!}$$

整理一下

$$\sum\limits_{i=0}^{\infty}n^i \sum\limits_{j=i}^{\infty}\frac{(-1)^{j-i}s_j^ix^j}{j!}=\sum\limits_{i=0}^{\infty}\frac{n^i\ln(x+1)^i}{i!}$$

两边约掉

$$\sum\limits_{j=i}^{\infty}\frac{(-1)^{j-i}s_j^ix^j}{j!}=\frac{\ln(x+1)^i}{i!}$$

这样就没了啊。。。用多项式$\ln$和快速幂做，时间复杂度$O(n\log n)$

第一类斯特林数·行

Luogu P5408

应$\texttt{M}$$\texttt{_sea}$的要求，这里终于不咕咕了。

这里可是最最最卡常的地方了！

首先，我们可以自然的想到一个做法。原理是这样

$$x^{\overline n}=\sum\limits_{i=0}^ns_n^ix^i$$

而

$$x^{\overline n}=\prod_{i=0}^{n-1}(x+i)$$

所以考虑直接分治乘法即可，时间复杂度$O(n\log^2n)$

可是这样过不去。考虑倍增，有

$$x^{\overline{2n}}=x^{\overline n}(x+n)^{\overline n}$$

假设$F(x)=x^{\overline n}$，我们当前的目标是求出$F(x+n)$，所以

$$F(x+n)=\sum\limits_{i=0}^{n}f_i(x+n)^i$$

强行展开

$$F(x+n)=\sum\limits_{i=0}^{n}f_i\sum\limits_{j=0}^{i}C_i^jn^{i-j}x^j$$

合并一下

$$F(x+n)=\sum\limits_{j=0}^{n}\frac{x^j}{j!}\sum\limits_{i=0}^{j}i!f_i\frac{n^{j-i}}{(j-i)!}$$

把$i!f_i$翻转一下做一次卷积即可。时间复杂度$O(n\log n)$，要卡卡常。