Skip to content

3317. Find the Number of Possible Ways for an Event

Description

You are given three integers n, x, and y.

An event is being held for n performers. When a performer arrives, they are assigned to one of the x stages. All performers assigned to the same stage will perform together as a band, though some stages might remain empty.

After all performances are completed, the jury will award each band a score in the range [1, y].

Return the total number of possible ways the event can take place.

Since the answer may be very large, return it modulo 109 + 7.

Note that two events are considered to have been held differently if either of the following conditions is satisfied:

  • Any performer is assigned a different stage.
  • Any band is awarded a different score.

 

Example 1:

Input: n = 1, x = 2, y = 3

Output: 6

Explanation:

  • There are 2 ways to assign a stage to the performer.
  • The jury can award a score of either 1, 2, or 3 to the only band.

Example 2:

Input: n = 5, x = 2, y = 1

Output: 32

Explanation:

  • Each performer will be assigned either stage 1 or stage 2.
  • All bands will be awarded a score of 1.

Example 3:

Input: n = 3, x = 3, y = 4

Output: 684

 

Constraints:

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

Solutions

Solution 1: Dynamic Programming

Thinking

Performers occupy at most \(x\) nonempty stages, and each stage then chooses one of \(y\) scores. With \(n,x \le 1000\), we can DP on people versus stages used.

Person \(i\) either joins one of the \(j\) existing stages or opens a new one among the \(x-j+1\) unused stages. These cases partition every assignment.

After \(n\) people, each \(j\) is multiplied by \(y^j\) for the stage scores, and the sum is taken modulo \(10^9+7\).

We define \(f[i][j]\) to represent the number of ways to arrange the first \(i\) performers into \(j\) programs. Initially, \(f[0][0] = 1\), and the rest \(f[i][j] = 0\).

For \(f[i][j]\), where \(1 \leq i \leq n\) and \(1 \leq j \leq x\), we consider the \(i\)-th performer:

  • If the performer is assigned to a program that already has performers, there are \(j\) choices, i.e., \(f[i - 1][j] \times j\);
  • If the performer is assigned to a program that has no performers, there are \(x - (j - 1)\) choices, i.e., \(f[i - 1][j - 1] \times (x - (j - 1))\).

So the state transition equation is:

\[ f[i][j] = f[i - 1][j] \times j + f[i - 1][j - 1] \times (x - (j - 1)) \]

For each \(j\), there are \(y^j\) choices, so the final answer is:

\[ \sum_{j = 1}^{x} f[n][j] \times y^j \]

Note that since the answer can be very large, we need to take the modulo \(10^9 + 7\).

The time complexity is \(O(n \times x)\), and the space complexity is \(O(n \times x)\). Here, \(n\) and \(x\) represent the number of performers and the number of programs, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def numberOfWays(self, n: int, x: int, y: int) -> int:
        mod = 10**9 + 7
        f = [[0] * (x + 1) for _ in range(n + 1)]
        f[0][0] = 1
        for i in range(1, n + 1):
            for j in range(1, x + 1):
                f[i][j] = (f[i - 1][j] * j + f[i - 1][j - 1] * (x - (j - 1))) % mod
        ans, p = 0, 1
        for j in range(1, x + 1):
            p = p * y % mod
            ans = (ans + f[n][j] * p) % mod
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int numberOfWays(int n, int x, int y) {
        final int mod = (int) 1e9 + 7;
        long[][] f = new long[n + 1][x + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= x; ++j) {
                f[i][j] = (f[i - 1][j] * j % mod + f[i - 1][j - 1] * (x - (j - 1) % mod)) % mod;
            }
        }
        long ans = 0, p = 1;
        for (int j = 1; j <= x; ++j) {
            p = p * y % mod;
            ans = (ans + f[n][j] * p) % mod;
        }
        return (int) ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numberOfWays(int n, int x, int y) {
        const int mod = 1e9 + 7;
        long long f[n + 1][x + 1];
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= x; ++j) {
                f[i][j] = (f[i - 1][j] * j % mod + f[i - 1][j - 1] * (x - (j - 1) % mod)) % mod;
            }
        }
        long long ans = 0, p = 1;
        for (int j = 1; j <= x; ++j) {
            p = p * y % mod;
            ans = (ans + f[n][j] * p) % mod;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func numberOfWays(n int, x int, y int) int {
    const mod int = 1e9 + 7
    f := make([][]int, n+1)
    for i := range f {
        f[i] = make([]int, x+1)
    }
    f[0][0] = 1
    for i := 1; i <= n; i++ {
        for j := 1; j <= x; j++ {
            f[i][j] = (f[i-1][j]*j%mod + f[i-1][j-1]*(x-(j-1))%mod) % mod
        }
    }
    ans, p := 0, 1
    for j := 1; j <= x; j++ {
        p = p * y % mod
        ans = (ans + f[n][j]*p%mod) % mod
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function numberOfWays(n: number, x: number, y: number): number {
    const mod = BigInt(10 ** 9 + 7);
    const f: bigint[][] = Array.from({ length: n + 1 }, () => Array(x + 1).fill(0n));
    f[0][0] = 1n;
    for (let i = 1; i <= n; ++i) {
        for (let j = 1; j <= x; ++j) {
            f[i][j] = (f[i - 1][j] * BigInt(j) + f[i - 1][j - 1] * BigInt(x - (j - 1))) % mod;
        }
    }
    let [ans, p] = [0n, 1n];
    for (let j = 1; j <= x; ++j) {
        p = (p * BigInt(y)) % mod;
        ans = (ans + f[n][j] * p) % mod;
    }
    return Number(ans);
}

Comments