下降幂多项式的简单小应用

看 lyx 的 《〈具体数学〉选讲》学的,不知道哪里有更好的材料 /kk

这篇是自己做笔记用的,要学更建议看原 PPT(

基础知识

下降幂:

\[x^\underline{m}=x(x-1)\cdots(x-m+1)=m!{x\choose m}=\frac{x!}{(x-m)!} \]

下降幂的差分:

\[(x+1)^{\underline m}-x^{\underline m}=mx^\underline{m-1} \]

下降幂的定和式:

\[\sum_{a\le x<b}x^\underline m=\frac{b^\underline{m+1}-a^\underline{m+1}}{m+1} \]

可见,下降幂形式做差分、求和、偏移等操作都很方便。

往往在出现连续点值的时候,要想到转下降幂。

下降幂和组合数的关系说不定还可以带来一些组合意义。

算法

下降幂多项式与普通多项式的互相转换?FFT 是【10】的,鸽。

只要平方的话,就

\(\sum_{i\ge 0} a_ix^i\)
\(=\sum_{i\ge 0} a_i\sum_{j=0}^i{i\brace j}x^\underline j\)
\(=\sum_{j\ge 0}(\sum_{i\ge j} a_i{i\brace j})x^\underline j\)

转回来也是一样,用第一类斯特林数。

例题

比如 如何优雅地求和 就是和连续点值有关系,也可以用下降幂做。还被拿去弱化搬到联合省选。但这里不讲。

OSU!

有一个大小为 \(n\) 的数组,其第 \(i\) 个位置有 \(p_i\) 的概率为 \(1\),\(1-p_i\) 的概率为 \(0\)。
求这个数组中 \(1\) 的极长连续段长度的 \(k\) 次方和的期望。
对大质数取模,\(n\le 10^7,k\le 10\)

比较简单的做法是设 \(f_{i,j}\) 表示以 \(i\) 结尾的极长连续段长度的 \(j\) 次方的期望,每个位置上的转移有 \(O(k^2)\),是因为要用二项式定理 \((x+1)^k=\sum_{j=0}^kx^j{x\choose j}\)。

注意到是连续点值,以及转移时有把底数加一的操作,考虑用下降幂多项式来做。这样的话,我们做的类似的事情是 \((x+1)^\underline k=x^\underline k+kx^\underline{k-1}\),每个位置上的转移只有 \(O(k)\) 了。

求最后答案时可以直接使用第二类斯特林数。

时间复杂度 \(O(nk)\)。

小技巧:可以用 \(\sum_{i\ge 0} a_ix^\underline i\) 的时候一般也可以用 \(\sum_{i\ge 0} a_i{x\choose i}\),有可能会更方便。

作业

给出 \(n,m\) 和 \(a_1,a_2,\cdots,a_n\),求有多少序列 \(b_1,b_2,\cdots,b_n\) 使得 \(a_i\le b_i\le m\) 且 \(b_i\le b_{i+1}\)。
\(n\le 5000,0\le a_i\le m\le 10^9\),对 \(1\ 000\ 000\ 007\) 取模

为了方便,\(a_i\gets \max_{j=1}^ia_j,a_{n+1}\gets m\)。

设 \(f_{i,j}\) 表示有多少种合法的 \(b_1,b_2\cdots,b_i\) 使 \(b_i=j\)。

\(f_{i,j}=\sum_{k=a_{i-1}}^jf_{i-1,k}\)

答案即为 \(f_{n+1,m}\)。但是 \(m\) 巨大,暴力 dp 无法接受。

注意到固定 \(i\) 时,\(f_{i,j}\) 是不超过 \(i-1\) 次的多项式的连续点值,考虑设 \(\sum_{0\le j<i}g_{i,j}x^\underline j=F_i(x)=f_{i,x}\)。

\(F_{i+1}(x)=\sum_{y=a_{i}}^xF_{i}(y)\)
\(=\sum_{y=a_{i}}^x\sum_{0\le j<i}g_{i,j}y^\underline j\)
\(=\sum_{0\le j<i}g_{i,j}\sum_{y=a_{i}}^xy^\underline j\)
\(=\sum_{0\le j<i}g_{i,j}\frac{1}{j+1}((x+1)^\underline{j+1}-a_{i}^\underline{j+1})\)
\(=\sum_{0\le j<i}g_{i,j}\frac{1}{j+1}(x^\underline{j+1}+(j+1)x^\underline j-a_{i}^\underline{j+1})\)

这样就可以直接在 \(g\) 之间转移了,最后展开计算 \(F_{n+1}(m)\) 即可,时间复杂度 \(O(n^2)\)。


其实见得比较少那种 原本是下降幂 转成普通幂做特别优的题,但也不失为一种思路。

上一篇:C语言-八进制转十进制


下一篇:#Raney引理,圆排列#洛谷 6672 [清华集训2016] 你的生命已如风中残烛