闲话

为啥最近在讲解板子呢？
主要是最近过年了 就不动脑子了（

拜年祭！拜年祭！拜年祭！
去 bilibili 233 直播间可以砍很可爱寐寐

大家！除夕快乐！
冒泡排序，选择排序，插入排序，快速排序，堆排序，归并排序，希尔排序，桶排序，基数排序新年帮您排忧解难；
有向图，无向图，有环图，无环图，完全图，稠密图，稀疏图，拓扑图，广义串并联图祝您新年宏图大展；
最短路，最长路，单源路径，多源路径祝您新年路路通畅；
线段树，红黑树，最小生成树，Trie 树，van Emde Boas树祝您新年好运枝繁叶茂；
最大流，网络流，标准输入流，标准输出流，文件输入流，文件输出流祝您新年顺顺流流；
线性动规，区间动规，坐标动规，背包动规，树型动归为您的新年规划精彩；
散列表，哈希表，邻接表，双向链表，循环链表帮您在新年表达喜悦；
\(O(1), O(\log n), O(n), O(n\log n), O(n^2), O(n^3), O(2^n), O(n!)\) 祝大家新年渐进步步高！

下降幂多项式

下降幂多项式是一类形式幂级数，其中占位元 \(k_n(x) = x^{\underline n}\)。具体地，我们定义一个截断在 \(x^{\underline {n + 1}}\) 项的下降幂多项式形如

下降幂多项式是一类有着良好性质的多项式。具体地，我们关注下降幂多项式的前 \(i\) 项点值。要做到这件事，首先需要写出点值的 egf。

可以看到，一个下降幂多项式的点值的 egf 就是它系数一一对应的普通多项式卷上 \(e^x\)。
我们不难在 \(O(n)\) 的时间内得到 \(e^x\)，因此得到一个下降幂多项式的复杂度就是 \(O(\text M(n))\)，常数很小。

这样我们可以轻松做到下降幂多项式卷积。得到点值后就可以按位相乘并消去其中一个系数中带着的阶乘就能得到卷积点值的 egf。然后做逆运算即可，做法就是卷上 \(e^{-x}\)，这个也可以 \(O(\text M(n))\) 地得到。

有人把这种操作和逆操作叫做 \(\text{FDT}\) 和 \(\text{IFDT}\)。感觉挺独特？

Submission.

signed main() {
	cin >> n >> m;
	A.resize(n + m + 1), B.resize(n + m + 1), E.resize(n + m + 1);
	rep(i,0,n) cin >> A[i]; rep(i,0,m) cin >> B[i];
	rep(i,0,n+m) E[i] = gifc(i);
	A *= E, B *= E; A.resize(n + m + 1), B.resize(n + m + 1);
	for (int i = 0; i <= n + m; ++ i)
		A[i] = 1ll * A[i] * B[i] % mod * gfac(i) % mod;
	rep(i,0,n+m) E[i] = ((i & 1) ? mod - gifc(i) : gifc(i));
	A *= E;
	cout << A.slice(n + m) << '\n';
}

然后我们也可以做到普通多项式和下降幂多项式的互相转换。

我们不是能快速得到下降幂多项式的点值嘛，那就应用多点求值技术吧！

普通多项式转下降幂多项式的话，直接多点求值得到前 \(n\) 项系数，然后做 \(\text{IFDT}\) 即可。Submission.
下降幂多项式转普通多项式的话，直接做 \(\text{FDT}\) 得到系数，然后快速插值即可。这一步由于是连续点值所以可以应用性质得到更快的做法，不用直接上板子。Submission.

直接做的复杂度是 \(O(\text M(n)\log n)\) 的，还是有点劣的。

板子之后再封装一下吧。可以用我的首页链接查看！