3317. 找到事件的可能方案数

Hard

题目描述

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

一场活动正在为 n 位表演者举办。当表演者到达时，他们被分配到 x 个舞台中的一个。分配到同一舞台的所有表演者将作为一个乐队一起表演，不过一些舞台可能保持空置。

所有表演结束后，评审团将为每个乐队评分，分数范围为 [1, y]。

返回活动可能举办的总方案数。

由于答案可能很大，请返回对 109 + 7 取模的结果。

注意，如果满足以下任一条件，则认为两个活动的举办方式不同：

任何表演者被分配到不同的舞台。
任何乐队被授予不同的分数。

示例 1：

输入：n = 1, x = 2, y = 3
输出：6
解释：
- 有 2 种方式为表演者分配舞台。
- 评审团可以为唯一的乐队评 1、2 或 3 分。

示例 2：

输入：n = 5, x = 2, y = 1
输出：32
解释：
- 每个表演者将被分配到舞台 1 或舞台 2。
- 所有乐队将被评 1 分。

示例 3：

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

约束条件：

1 <= n, x, y <= 1000

解题思路

这是一个组合数学问题，需要使用动态规划和容斥原理。

核心思路：

问题分解：我们需要计算将 n 个表演者分配到最多 x 个舞台，且每个有表演者的舞台都有评分的方案数。
关键观察：
- 每个表演者可以选择任意一个舞台，但我们只关心有表演者的舞台
- 对于有 k 个舞台有表演者的情况，每个舞台都需要评分
解法思路：
- 枚举实际使用的舞台数量 k（1 到 min(n,x)）
- 对于固定的 k，计算将 n 个表演者分配到恰好 k 个舞台的方案数
- 使用容斥原理：先允许任意分配到 k 个舞台，然后减去有空舞台的情况
具体计算：
- 选择 k 个舞台：C(x,k)
- 将 n 个表演者分配到 k 个舞台，确保每个舞台都有人：使用容斥原理计算
- 每个有表演者的舞台评分：y^k
容斥原理：将 n 个表演者分配到恰好 k 个非空舞台的方案数为： ∑(i=0 to k) (-1)^i * C(k,i) * (k-i)^n

代码实现

class Solution {
public:
    int numberOfWays(int n, int x, int y) {
        const int MOD = 1e9 + 7;
        
        // 预计算组合数
        vector<vector<long long>> C(x + 1, vector<long long>(x + 1, 0));
        for (int i = 0; i <= x; 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;
            }
        }
        
        // 预计算幂次
        auto power = [&](long long base, long long exp) -> long long {
            long long result = 1;
            base %= MOD;
            while (exp > 0) {
                if (exp & 1) result = (result * base) % MOD;
                base = (base * base) % MOD;
                exp >>= 1;
            }
            return result;
        };
        
        long long answer = 0;
        
        // 枚举实际使用的舞台数
        for (int k = 1; k <= min(n, x); k++) {
            // 选择k个舞台
            long long ways_to_choose_stages = C[x][k];
            
            // 使用容斥原理计算n个人分配到恰好k个非空舞台的方案数
            long long ways_to_assign = 0;
            for (int i = 0; i <= k; i++) {
                long long term = (C[k][i] * power(k - i, n)) % MOD;
                if (i & 1) {
                    ways_to_assign = (ways_to_assign - term + MOD) % MOD;
                } else {
                    ways_to_assign = (ways_to_assign + term) % MOD;
                }
            }
            
            // 每个舞台的评分
            long long ways_to_score = power(y, k);
            
            // 累加到答案
            long long contribution = (((ways_to_choose_stages * ways_to_assign) % MOD) * ways_to_score) % MOD;
            answer = (answer + contribution) % MOD;
        }
        
        return answer;
    }
};

class Solution:
    def numberOfWays(self, n: int, x: int, y: int) -> int:
        MOD = 10**9 + 7
        
        # 预计算组合数
        C = [[0] * (x + 1) for _ in range(x + 1)]
        for i in range(x + 1):
            C[i][0] = 1
            for j in range(1, i + 1):
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
        
        def power(base, exp):
            result = 1
            base %= MOD
            while exp > 0:
                if exp & 1:
                    result = (result * base) % MOD
                base = (base * base) % MOD
                exp >>= 1
            return result
        
        answer = 0
        
        # 枚举实际使用的舞台数
        for k in range(1, min(n, x) + 1):
            # 选择k个舞台
            ways_to_choose_stages = C[x][k]
            
            # 使用容斥原理计算n个人分配到恰好k个非空舞台的方案数
            ways_to_assign = 0
            for i in range(k + 1):
                term = (C[k][i] * power(k - i, n)) % MOD
                if i & 1:
                    ways_to_assign = (ways_to_assign - term + MOD) % MOD
                else:
                    ways_to_assign = (ways_to_assign + term) % MOD
            
            # 每个舞台的评分
            ways_to_score = power(y, k)
            
            # 累加到答案
            contribution = (ways_to_choose_stages * ways_to_assign % MOD * ways_to_score) % MOD
            answer = (answer + contribution) % MOD
        
        return answer

public class Solution {
    public int NumberOfWays(int n, int x, int y) {
        const int MOD = 1000000007;
        
        // 预计算组合数
        long[,] C = new long[x + 1, x + 1];
        for (int i = 0; i <= x; 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;
            }
        }
        
        long Power(long baseNum, long exp) {
            long result = 1;
            baseNum %= MOD;
            while (exp > 0) {
                if ((exp & 1) == 1) result = (result * baseNum) % MOD;
                baseNum = (baseNum * baseNum) % MOD;
                exp >>= 1;
            }
            return result;
        }
        
        long answer = 0;
        
        // 枚举实际使用的舞台数
        for (int k = 1; k <= Math.Min(n, x); k++) {
            // 选择k个舞台
            long waysToChooseStages = C[x, k];
            
            // 使用容斥原理计算n个人分配到恰好k个非空舞台的方案数
            long waysToAssign = 0;
            for (int i = 0; i <= k; i++) {
                long term = (C[k, i] * Power(k - i, n)) % MOD;
                if ((i & 1) == 1) {
                    waysToAssign = (waysToAssign - term + MOD) % MOD;
                } else {
                    waysToAssign = (waysToAssign + term) % MOD;
                }
            }
            
            // 每个舞台的评分
            long waysToScore = Power(y, k);
            
            // 累加到答案
            long contribution = (waysToChooseStages * waysToAssign % MOD * waysToScore) % MOD;
            answer = (answer + contribution) % MOD;
        }
        
        return (int)answer;
    }
}

var numberOfWays = function(n, x, y) {
    const MOD = 1e9 + 7;
    
    // 预计算组合数
    const C = Array(x + 1).fill(null).map(() => Array(x + 1).fill(0));
    for (let i = 0; i <= x; i++) {
        C[i][0] = 1;
        for (let j = 1; j <= i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
    
    function power(base, exp) {
        let result = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp & 1) result = (result * base) % MOD;
            base = (base * base) % MOD;
            exp = Math.floor(exp / 2);
        }
        return result;
    }
    
    let answer = 0;
    
    // 枚举实际使用的舞台数
    for (let k = 1; k <= Math.min(n, x); k++) {
        // 选择k个舞台
        const waysToChooseStages = C[x][k];
        
        // 使用容斥原理计算n个人分配到恰好k个非空舞台的方案数
        let waysToAssign = 0;
        for (let i = 0; i <= k; i++) {
            const term = (C[k][i] * power(k - i, n)) % MOD;
            if (i & 1) {
                waysToAssign = (waysToAssign - term + MOD) % MOD;
            } else {
                waysToAssign = (waysToAssign + term) % MOD;
            }
        }
        
        // 每个舞台的评分
        const waysToScore = power(y, k);
        
        // 累加到答案
        const contribution = (waysToChooseStages * waysToAssign % MOD * waysToScore) % MOD;
        answer = (answer + contribution) % MOD;
    }
    
    return answer;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	大小
时间复杂度	O(x²)
空间复杂度	O(x²)

其中预计算组合数需要 O(x²)，枚举舞台数和容斥计算也是 O(x²)，快速幂计算为 O(log y)。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目