Skip to content

Latest commit

 

History

History
232 lines (178 loc) · 6.55 KB

README_EN.md

File metadata and controls

232 lines (178 loc) · 6.55 KB
comments difficulty edit_url tags
true
Hard
Math
Dynamic Programming
Combinatorics

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.

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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);
}