Welcome to Subscribe On Youtube
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
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.
-
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; } }
-
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; } };
-
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
-
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 }
-
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); }