题目链接：TopCoder SRM 686 B

求所有长度为 $n$ 的置换的循环数量之和的 $m$ 次方。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 300$，$1 \le n \le 10 ^ {5}$，$0 \le m \le 300$。

$$ \gdef\stra#1#2{\begin{bmatrix} #1 \\ #2 \end{bmatrix}} \gdef\strb#1#2{\begin{Bmatrix} #1 \\ #2 \end{Bmatrix}} $$

Solution

枚举循环数量：

$$ \sum_{i = 1} ^ {n} \stra{n}{i} i ^ m $$

对 $i ^ m$ 进行第二类斯特林数展开：

$$ \sum_{i = 1} ^ {n} \stra{n}{i} \sum_{j = 0} ^ {m} \strb{m}{j} i ^ {\underline{j}} $$

变换求和顺序：

$$ \begin{aligned} & \sum_{j = 0} ^ {m} \strb{m}{j} \sum_{i = 1} ^ {n} \stra{n}{i} i ^ {\underline{j}} \\ = & \sum_{j = 0} ^ {m} \strb{m}{j} j! \sum_{i = 1} ^ {n} \stra{n}{i} \binom{i}{j} \\ = & \sum_{j = 0} ^ {m} \strb{m}{j} j! \stra{n + 1}{j + 1} \end{aligned} $$

直接计算 $\mathcal O(nm)$ 个第一类斯特林数，$\mathcal O(m ^ 2)$ 个第二类斯特林数即可。

可以使用多项式的一些技巧做更大的 $n, m$。

时间复杂度：$\mathcal O(nm + Tm ^ 2)$。

Code

#include <bits/stdc++.h>
typedef long long int64;

const int N = 1e5 + 1, M = 3e2 + 1, MOD = 1e9 + 7;

class CyclesNumber {
private:
    int s1[N + 5][M + 5], s2[M + 5][M + 5], fac[M + 5];

    void init(int n, int m) {
        s1[0][0] = s2[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i && j <= m; j++) {
                s1[i][j] = (s1[i - 1][j - 1] + (int64)(i - 1) * s1[i - 1][j]) % MOD;
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= i; j++) {
                s2[i][j] = (s2[i - 1][j - 1] + (int64)j * s2[i - 1][j]) % MOD;
            }
        }
        fac[0] = 1;
        for (int i = 1; i <= m; i++) {
            fac[i] = (int64)fac[i - 1] * i % MOD;
        }
    }
    int solve(int n, int m) {
        int64 ans = 0;
        for (int i = 0; i <= m; i++) {
            ans += (int64)s2[m][i] * fac[i] % MOD * s1[n + 1][i + 1] % MOD;
        }
        return ans % MOD;
    }

public:
    std::vector<int> getExpectation(std::vector<int> n, std::vector<int> m) {
        init(N, M);
        std::vector<int> ans;
        for (int i = 0; i < (int)n.size(); i++) {
            ans.emplace_back(solve(n[i], m[i]));
        }
        return ans;
    }
};

Extend

具体证明一下最后一步变换：

$$ \sum_{i = 1} ^ {n} \stra{n}{i} \binom{i}{k} = \stra{n + 1}{k + 1} $$

组合意义是：对于所有长度为 $n$ 的置换，从中选出 $k$ 个循环的方案数之和。

考虑加入一个新的数字 $n + 1$，将所有没有选中的排列全部加入到 $n + 1$ 的循环中。

我们需要证明这样的构造是一个双射：

• 每个 $n$ 置换唯一对应一个 $n + 1$ 置换：

  • 对于一个循环，我们将其中的最大值记为「首位」并放在第一个位置，其余数字顺次连接：如 $9-2-6-1$。
  • 对于没有选中的循环，我们按照他们「首位」从小到大加入 $n + 1$ 的循环中。

• 每个 $n + 1$ 置换唯一对应一个 $n$ 置换：

  • 可以发现，对 $n + 1$ 所在的循环构造一个递增的单调栈，就可以还原所有循环。

证毕。