「TopCoder SRM 686B」CyclesNumber

题目链接:TopCoder SRM 686B

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

本题有 $T$ 组数据。

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

$$ \newcommand{\stra}[2]{\begin{bmatrix} #1 \\ #2 \end{bmatrix}} \newcommand{\strb}[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{align} & \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{align} $$

直接计算 $\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$ 所在的循环构造一个递增的单调栈,就可以还原所有循环。

证毕。

发表评论