题目描述

给你三个整数 n，x 和 y。

一个活动总共有 n 位表演者。每一位表演者会 被安排 到 x 个节目之一，有可能有节目 没有 任何表演者。

所有节目都安排完毕后，评委会给每一个 有表演者的 节目打分，分数是一个 [1, y] 之间的整数。

请你返回 总 的活动方案数。

答案可能很大，请你将它对 10^9 + 7 取余 后返回。

注意，如果两个活动满足以下条件 之一，那么它们被视为 不同 的活动：

• 存在 一个表演者在不同的节目中表演。
• 存在 一个节目的分数不同。

样例

输入：n = 1, x = 2, y = 3

输出：6

解释：

表演者可以在节目 1 或者节目 2 中表演。
评委可以给这唯一一个有表演者的节目打分 1，2 或者 3。

输入：n = 5, x = 2, y = 1

输出：32

解释：

每一位表演者被安排到节目 1 或者 2。
所有的节目分数都为 1。

输入：n = 3, x = 3, y = 4

输出：684

限制

• 1 <= n, x, y <= 1000

算法

(数学) $O(nx)$

1. 分步求解，先从 $x$ 个节目中选择 $i$ 个节目进行表演，共 $C(x, i)$ 种方法。每个节目的打分总计 $y^i$ 种方法。
2. 接下来求解 $n$ 个人表演 $i$ 个不同节目的方案数，且每个节目需要至少有一个人表演，通过动态规划求解。
3. 设 $f(i, j)$ 表示 $i$ 个人分配给 $j$ 个节目的方案数。转移时，考虑第 $i$ 个人的分配，第一个人可以分配给前 $j$ 个节目中的任意一个，则转移 $f(i, j) = f(i, j) + f(i - 1, j) * j$，也可以单独新开第 $j$ 个节目，有 $j$ 种方式排列，则转移 $f(i, j) = f(i, j) + f(i - 1, j - 1) * j$。

时间复杂度

• 预处理的时间复杂度为 $O(nx)$，枚举答案的时间复杂度为 $O(\min(n, x))$，故总时间复杂度为 $O(nx)$。

空间复杂度

• 需要 $O(nx)$ 的额外空间存储预处理的状态。

C++ 代码

#define LL long long

const int N = 1010, mod = 1000000007;

int C[N][N], f[N][N];

auto init = []{
    for (int i = 0; i < N; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }

    f[0][0] = 1;
    for (int i = 1; i < N; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = (LL)(f[i - 1][j - 1] + f[i - 1][j]) * j % mod;

    return 0;
}();

class Solution {
public:
    int numberOfWays(int n, int x, int y) {
        int ans = 0, p = 1;

        for (int i = 1; i <= min(n, x); i++) {
            p = (LL)(p) * y % mod;
            ans = (ans + (LL)(C[x][i]) * f[n][i] % mod * p % mod) % mod;
        }

        return ans;
    }
};