问题标题: 洛谷：3711 几何图形

不知道为什么这题把自然数幂和函数的求和上限额外加了一个1，这样的话我们可能需要用二项式定理重新把原来的式子展开一遍……

前置芝士：伯努利数

如果不会伯努利数的话可以看一下这篇博客学习一下

前置芝士：多项式求逆

蛤？不会多项式求逆，可以出门左转你站模板区去学习一下

前置芝士：快速处理伯努利数

我们使用伯努利数的指数型生成函数来快速的预处理它

具体来讲我们有这样一个和式

\sum_{i}\frac{B(i)}{i!}z^{i}=\frac{z}{e^{z}-1}i∑​i!B(i)​zi=ez−1z​

等会显然左边是一个无限和式，这东西显然没有办法计算啊

没关系啊，我们把e^{z}ez大力泰勒展开一下

e^{z}=\sum_{i}\frac{z^{i}}{i!}ez=i∑​i!zi​

那么我们要计算的式子就是

\frac{z}{\sum_{i}\frac{z^{i}}{i!}-1}∑i​i!zi​−1z​

然后我们发现一个很尴尬的事实，这东西分母常数项是0求不了逆……

还好分子是zz所以我们上下同时除一个zz

\frac{1}{\sum_{i}\frac{z^{i}}{(i+1)!}}∑i​(i+1)!zi​1​

那这样的话我们就可以愉快的多项式求逆然后把伯努利数的前nn项刷出来了~

本题题解

众所周知，标准的自然数幂和函数S(n,k)S(n,k)是等于\sum_{i=0}^{n-1}i^{k}∑i=0n−1​ik的但是这题我们的循环上限变成了nn这就十分的难受了

所以设答案函数是f(n)f(n)，我们先计算比较好算的f(n-1)f(n−1)然后再用一些科技把答案的系数展开就好了

那么在以下的讨论当中我们认为S(n,k)S(n,k)代表\sum_{i=0}^{n-1}i^{k}∑i=0n−1​ik而不是\sum_{i=0}^{n}i^{k}∑i=0n​ik

题目中让我们求

\sum_{k=0}^{n}S(n,k)a(k)k=0∑n​S(n,k)a(k)

强行用伯努利数展开一波可以得到

\sum_{k=0}^{n}a(k)\frac{1}{k+1}\sum_{i=0}^{k}{k+1 \choose i}B(i)n^{k+1-i}k=0∑n​a(k)k+11​i=0∑k​(ik+1​)B(i)nk+1−i

接下来我们翻转后半部分的求和顺序

\sum_{k=0}^{n}a(k)\frac{1}{k+1}\sum_{i=1}^{k+1}{k+1 \choose k+1-i}B(k+1-i)n^{i}k=0∑n​a(k)k+11​i=1∑k+1​(k+1−ik+1​)B(k+1−i)ni

让我们把组合数拆了搞成阶乘的形式

\sum_{k=0}^{n}a(k)k!\sum_{i=1}^{k+1}\frac{B(k+1-i)}{(k+1-i)!}\frac{n^{i}}{i!}k=0∑n​a(k)k!i=1∑k+1​(k+1−i)!B(k+1−i)​i!ni​

接下来又是喜闻乐见的交换求和号环节了

\sum_{i=1}^{n+1}\frac{n^{i}}{i!}\sum_{k=i-1}^{n}a(k)k!\frac{B(k+1-i)}{(k+1-i)!}i=1∑n+1​i!ni​k=i−1∑n​a(k)k!(k+1−i)!B(k+1−i)​

如果我们令f,gf,g分别表示这两个式子的话

f(i)=\frac{B(i)}{i!}f(i)=i!B(i)​

g(i)=a(i)i!g(i)=a(i)i!

式子会被写的好看一点

\sum_{i=1}^{n+1}\frac{n^i}{i!}\sum_{p-q=i-1}f(p)g(q)i=1∑n+1​i!ni​p−q=i−1∑​f(p)g(q)

似乎是个差卷积，众所周知我们的ntt只能处理和的卷积，所以让我们把g函数翻转一下

g_{r}(x)=g(n-x)gr​(x)=g(n−x)

那么原来的式子就会变成

\sum_{i=1}^{n+1}\frac{n^i}{i!}\sum_{p+q=n+(i-1)}f(p)g_{r}(q)i=1∑n+1​i!ni​p+q=n+(i−1)∑​f(p)gr​(q)

这样的话我们一波ntt然后除上一个阶乘就可以求出f(n-1)f(n−1)第i项系数了，让我们设这个东西为c_{i}ci​接下来我们要做的是求出这个多项式的系数

\sum_{i=1}^{n+1}c_{i}(x+1)^{i}i=1∑n+1​ci​(x+1)i

做法简单粗暴，直接二项式定理展开一下

\sum_{i=1}^{n+1}c_{i}\sum_{j=0}^{i}{i\choose j}x^{j}i=1∑n+1​ci​j=0∑i​(ji​)xj

让我们继续交换求和号，由于c_{0}=0c0​=0所以我们无需担心求和下界的问题

\sum_{j=0}^{n+1}x^{j}\sum_{i=j}^{n+1}{i\choose j}c_{i}j=0∑n+1​xji=j∑n+1​(ji​)ci​

把组合数用阶乘拆了可以得到

\sum_{j=0}^{n+1}x^{j}\frac{1}{j!}\sum_{i=j}^{n+1}c_{i}i!×\frac{1}{(i-j)!}j=0∑n+1​xjj!1​i=j∑n+1​ci​i!×(i−j)!1​

设f,gf,g分别为

f(i)=c_{i}i!f(i)=ci​i!

g(i)=\frac{1}{i!}g(i)=i!1​

那么我们会得到这样一个式子

\sum_{j=0}^{n+1}x^{j}\frac{1}{j!}\sum_{p-q=j}f(p)g(q)j=0∑n+1​xjj!1​p−q=j∑​f(p)g(q)

看起来又是烦人的差卷积，没关系接着翻转数列,令

g_{r}(x)=g(n+1-x)gr​(x)=g(n+1−x)

则原式为

\sum_{j=0}^{n+1}x^{j}\frac{1}{j!}\sum_{p+q=n+1+j}f(p)g(q)j=0∑n+1​xjj!1​p+q=n+1+j∑​f(p)g(q)

然后我们大力ntt一波除个阶乘就行了

不是原创，望采纳谢谢