一个和prufer序相关的组合问题

对于所有长为 \(n\) 值域在 \([1,m]\) 的正整数序列，对于每一个 \(1\leqslant i \leqslant m\) 记 \(c_{i}\) 表示 \(i\) 在 \(a\) 中的出现次数，定义其权值为 \(\prod_{i=1}^{m}c_{i}^{c_{i}+k}\)，求所有序列的权值和对一个大质数 \(p\) 取模的结果(特别的,我们定义 \(0^0=1\)，且对于负整数 \(k,0^k=0\))

数据范围：\(n\leqslant 5\times 10^6,-10\leqslant k \leqslant 10\)，\(k\) 为整数。

当 \(k=-1\) 时考虑 \(i^{i−1}\) 的组合意义：大小为 \(i\) 的有标号有根树数量，答案即把 \(n\) 个有标号点分为 \(m\) 棵有根有标号树的方案数。加一个超级根 \(0\)，并钦定 \(deg_{0}=m\)，且和 \(0\) 相连的点为根即可，答案为 \(mn^{n-m-1}m!\binom{n}{m}\)。

当 \(k=0\) 时可以设计一个这样的组合意义：大小为 \(i\) 的有标号有根树森林，设树的个数为 \(t\)，定义该森林的权值为 \(t!\)，则所有森林权值和为 \(i^i\) 。证明：\(i^i\) 实际上可以视为一个大小为 \(i\) 的无根树，选一条允许为单点的有向链，现在将有向链上的边断掉，如果形成了 \(d\) 棵有根树，那么串回成原来的就有 \(d!\) 种方案。现在考虑在合并时的生成函数，由于是 \(\text{EGF}\)，除以 \(d!\) 后变成了求 \([\frac{x^w}{w!}](\sum_{i=0}^{n}x^i)^m\)，即 如果最终形成了 \(w\) 个有根树，则方案数为 \(w!\binom{w+m-1}{m-1}\)。

现在对于任意的 \(k\)，可以想办法构造一个 \(val_{i}\) 满足 \(\sum_{j=0}^{i}ji^{i-j-1}val_{j}\binom{i}{j}=i^{i+k}\)，将其倒过来即 \(val_{i}=i^{i+k}-\sum_{j=0}^{i-1}ji^{i-j-1}val_{j}\binom{i}{j}\)，经过打表可以发现 \(val_{i}={i+k\brace i}i!\)(特别的对于 \(a<0\) 的 \(a\brace b\)，我们定义 \({a\brace b}=\sum_{i=0}^{b}(-1)^{b-i}\binom{b}{i}i^a\)，更加直观的解释其实是将 \(a\) 一开始就加上 \(p-1\)，此时 \({a\brace b}\equiv{a+p-1\brace b}\equiv\sum_{i=0}^{b}(-1)^{b-i}\binom{b}{i}i^{a+p-1}(\text{mod p})\)，这样的操作是好的，因为 \(i^{i+k}\equiv i^{i+k+p-1}(\text{mod p})\)。

接下来我们认为 \(k\geqslant 0\)，如果 \(k<0\) 可以将 \(k\) 置为 \(k+p-1\)，可以构造如下映射进行说明：

令 \(A\) 为长度为 \(n+k\) 值域在 \([1,n-1]\) 的序列构成的集合，令 \(B\) 为长度为 \(n-1\) 值域在 \([0,n]\) 的序列构成的集合，对于 \(B\)，如果其有 \(d\) 个 \(0\)，实际上对应着大小为 \(n\)，有 \(d+1\) 个有根树的森林。所以在这样的设计中，如果对于任意的 \(d\) 如果其对应的 \(A\) 中的序列个数都相同为 \(val_{d+1}\)，那么我们就得到了一组合法的 \(val\)。

实际上这个是成立的，令 \(a\in A\)，令一个指针 \(p\) 依次从小到大从 \(n\) 遍历到 \(n+k\)，每次进行如下操作：

令 \(q=a_{p}\)，将 \(a_{p}\) 置为 \(0\)，\(p\) 置为 \(q\)。

由于最后所有 \(i\geqslant n\) 的 \(a_{i}\) 全部变成了 \(0\)，可以将其删去，现在得到的 \(a\in B\)。于是只要对于每一个 \(b\in B\)，求有多少个 \(a\in A\) 可以得到它。令一个长度为 \(k+1\) 的序列 \(c\)，其中 \(c_{i}\) 表示 \(p=n+i-1\) 的初始加入时新增的不是自己的 \(0\) 的个数。

对于 \(p=n\) 时，其所产生的 \(0\) 构成了一条环外挂一条链的结构，将环接入链的那条边断掉后有 \(c_{1}!\) 种链的生成方案，而接入的那条边指向的点有 \(c_{1}+1\) 种方案(因为包括了 \(n\))，类似分析 \(p>n\) 的可以得到有 \(\prod_{i=1}^{k+1}c_{i}!(1+\sum_{j=1}^{i}c_{j})\) 种方案，对于所有 \(\sum_{i=1}^{k+1}c_{i}=d\) 求和得到的就是 \(val\) 的值(但由于要将所有 \(0\) 分配给不同的 \(c\)，所以还有 \(\frac{d!}{\prod_{i=1}^{k+1}c_{i}!}\) 的额外贡献)，实际上贡献为 \(d!\sum_{i=1}^{k+1}(1+\sum_{j=1}^{i}c_{j})=(d+1)!\sum_{i=1}^{k}(1+\sum_{j=1}^{i}c_{j})\)。

实际上相当于求所有正整数序列 \(s\) 满足 \(1\leqslant s_{1}\leqslant s_{2}\leqslant ...\leqslant s_{k}\leqslant d+1\)，贡献为 \((d+1)!\prod_{i=1}^{k}s_{i}\)，将其从左到右看作一条格路，将每次 \(s\) 的增加想象为新开一个盒子，将每次下标的向右移动想象为插入一个已有的盒子，需要新开 \(d+1\) 次盒子，插入 \(k\) 次已有的盒子，则可知方案数为 \({d+1+k\brace d+1}(d+1)!\)，实际上就是 \({i+k\brace i}i!\)。

于是令 \(F=(\sum_{i=0}^{n}{i+k\brace i}x^i)^m\)，则最终答案为 \(\sum_{i=1}^{n}in^{n-i-1}\binom{n}{i}[\frac{x^i}{i!}]F\)，对于 \(k<0\) 的部分，由于只有当 \(i+k<0\) 的时候 \(i+k\brace i\) 才有值，所以直接使用计算低阶多项式的 \(m\) 次幂的方法即可。

当 \(k>0\) 时，令 \(G_{i}=\sum_{i=0}^{\infty}{j+i\brace j}x^j\)，有 \(G_{0}=\frac{1}{1-x}\)，\(G_{i}=\frac{G_{i-1}'x}{1-x}\)，令 \(H_{i}=G_{i}(1-x)^{2i+1}\)，则 \(\frac{H_{i}}{(1-x)^{2i+1}}=\frac{{(\frac{H_{i-1}}{(1-x)^{2i-1}})'}x}{1-x}\)，化简可得 \(H_{i}=(H_{i-1}x)'+2iH_{i-1}-(H_{i-1}x^2)'\)，\(H\) 为一个 \(O(k)\) 阶多项式，实际上写出递推式后可以发现 \(H\) 就是二阶欧拉数。

现在相当于对于一个低阶多项式 \(W\)，要求 \((\frac{W}{(1-x)^{2k+1}})^m\)，这个同样可以用计算低阶多项式的 \(m\) 次幂的求导大法类似解决。

复杂度可以做到 \(O(nk)\)，同时对于 \(k=-2\) 的构成 \(n\) 个点 \(m\) 棵无根树的森林计数可以使用该做法导出一个容斥做法。