Find the Number of Possible Ways for an Event

Problem

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 10^9 + 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.

Examples

Example 1

1
2
3
4
5
6
7
8
9



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

1
2
3
4
5
6
7
8
9



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

1
2
3
4



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

Output: 684

Constraints

1 <= n, x, y <= 1000

Solution

Method 1 – Stars and Bars with Power for Band Scores

Intuition

Each performer can be assigned to any of the x stages, so there are x^n ways to assign performers. After assignment, each non-empty stage (band) gets a score from 1 to y. The number of non-empty bands can range from 1 to min(n, x). For each possible number of non-empty bands k, we count:

Ways to partition n performers into k non-empty bands: S(n, k) (Stirling numbers of the second kind).
Ways to assign these bands to x stages: P(x, k) = x! / (x-k)!.
Ways to assign scores to bands: y^k. Sum over all possible k.

Approach

Precompute factorials and inverse factorials up to max(n, x) for combinations and permutations.
Precompute Stirling numbers of the second kind S(n, k) for all k.
For each k from 1 to min(n, x):
- Compute ways = S(n, k) * P(x, k) * y^k.
- Add to the answer modulo 10^9 + 7.
Return the total sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution {
public:
    int numberOfWays(int n, int x, int y) {
        const int MOD = 1e9 + 7;
        vector<long long> fact(max(n, x) + 2, 1), invf(max(n, x) + 2, 1);
        for (int i = 1; i < fact.size(); ++i) fact[i] = fact[i-1] * i % MOD;
        invf.back() = powmod(fact.back(), MOD-2, MOD);
        for (int i = fact.size()-2; i >= 0; --i) invf[i] = invf[i+1] * (i+1) % MOD;
        auto perm = [&](int a, int b) -> long long {
            if (b > a) return 0;
            return fact[a] * invf[a-b] % MOD;
        };
        vector<vector<long long>> S(n+1, vector<long long>(x+1));
        S[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= x; ++j) {
                S[i][j] = (S[i-1][j-1] + S[i-1][j] * j) % MOD;
            }
        }
        long long ans = 0;
        for (int k = 1; k <= min(n, x); ++k) {
            long long ways = S[n][k] * perm(x, k) % MOD;
            long long score = powmod(y, k, MOD);
            ans = (ans + ways * score % MOD) % MOD;
        }
        return ans;
    }
    long long powmod(long long a, long long b, long long mod) {
        long long res = 1;
        while (b) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


func numberOfWays(n, x, y int) int {
    mod := int(1e9 + 7)
    maxv := n
    if x > n {
        maxv = x
    }
    fact := make([]int, maxv+2)
    invf := make([]int, maxv+2)
    fact[0] = 1
    for i := 1; i < len(fact); i++ {
        fact[i] = fact[i-1] * i % mod
    }
    invf[maxv+1] = powmod(fact[maxv+1], mod-2, mod)
    for i := maxv; i >= 0; i-- {
        invf[i] = invf[i+1] * (i+1) % mod
    }
    perm := func(a, b int) int {
        if b > a {
            return 0
        }
        return fact[a] * invf[a-b] % mod
    }
    S := make([][]int, n+1)
    for i := range S {
        S[i] = make([]int, x+1)
    }
    S[0][0] = 1
    for i := 1; i <= n; i++ {
        for j := 1; j <= x; j++ {
            S[i][j] = (S[i-1][j-1] + S[i-1][j]*j) % mod
        }
    }
    ans := 0
    for k := 1; k <= n && k <= x; k++ {
        ways := S[n][k] * perm(x, k) % mod
        score := powmod(y, k, mod)
        ans = (ans + ways*score%mod) % mod
    }
    return ans
}
func powmod(a, b, mod int) int {
    res := 1
    for b > 0 {
        if b&1 == 1 {
            res = res * a % mod
        }
        a = a * a % mod
        b >>= 1
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution {
    public int numberOfWays(int n, int x, int y) {
        int MOD = 1000000007;
        int maxv = Math.max(n, x);
        long[] fact = new long[maxv+2];
        long[] invf = new long[maxv+2];
        fact[0] = 1;
        for (int i = 1; i < fact.length; i++) fact[i] = fact[i-1] * i % MOD;
        invf[maxv+1] = powmod(fact[maxv+1], MOD-2, MOD);
        for (int i = maxv; i >= 0; i--) invf[i] = invf[i+1] * (i+1) % MOD;
        java.util.function.BiFunction<Integer, Integer, Long> perm = (a, b) -> b > a ? 0L : fact[a] * invf[a-b] % MOD;
        long[][] S = new long[n+1][x+1];
        S[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= x; j++) {
                S[i][j] = (S[i-1][j-1] + S[i-1][j] * j) % MOD;
            }
        }
        long ans = 0;
        for (int k = 1; k <= Math.min(n, x); k++) {
            long ways = S[n][k] * perm.apply(x, k) % MOD;
            long score = powmod(y, k, MOD);
            ans = (ans + ways * score % MOD) % MOD;
        }
        return (int)ans;
    }
    long powmod(long a, long b, long mod) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
    fun numberOfWays(n: Int, x: Int, y: Int): Int {
        val MOD = 1_000_000_007
        val maxv = maxOf(n, x)
        val fact = LongArray(maxv+2) { 1L }
        val invf = LongArray(maxv+2) { 1L }
        for (i in 1 until fact.size) fact[i] = fact[i-1] * i % MOD
        invf[maxv+1] = powmod(fact[maxv+1], MOD-2, MOD)
        for (i in maxv downTo 0) invf[i] = invf[i+1] * (i+1) % MOD
        fun perm(a: Int, b: Int) = if (b > a) 0L else fact[a] * invf[a-b] % MOD
        val S = Array(n+1) { LongArray(x+1) }
        S[0][0] = 1L
        for (i in 1..n) for (j in 1..x) S[i][j] = (S[i-1][j-1] + S[i-1][j] * j) % MOD
        var ans = 0L
        for (k in 1..minOf(n, x)) {
            val ways = S[n][k] * perm(x, k) % MOD
            val score = powmod(y.toLong(), k.toLong(), MOD)
            ans = (ans + ways * score % MOD) % MOD
        }
        return ans.toInt()
    }
    fun powmod(a: Long, b: Long, mod: Long): Long {
        var res = 1L; var aa = a; var bb = b
        while (bb > 0) {
            if (bb and 1L == 1L) res = res * aa % mod
            aa = aa * aa % mod
            bb = bb shr 1
        }
        return res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution:
    def numberOfWays(self, n: int, x: int, y: int) -> int:
        MOD = 10**9 + 7
        maxv = max(n, x)
        fact = [1] * (maxv + 2)
        invf = [1] * (maxv + 2)
        for i in range(1, len(fact)):
            fact[i] = fact[i-1] * i % MOD
        invf[-1] = pow(fact[-1], MOD-2, MOD)
        for i in range(len(fact)-2, -1, -1):
            invf[i] = invf[i+1] * (i+1) % MOD
        def perm(a, b):
            if b > a: return 0
            return fact[a] * invf[a-b] % MOD
        S = [[0] * (x+1) for _ in range(n+1)]
        S[0][0] = 1
        for i in range(1, n+1):
            for j in range(1, x+1):
                S[i][j] = (S[i-1][j-1] + S[i-1][j] * j) % MOD
        ans = 0
        for k in range(1, min(n, x)+1):
            ways = S[n][k] * perm(x, k) % MOD
            score = pow(y, k, MOD)
            ans = (ans + ways * score % MOD) % MOD
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


impl Solution {
    pub fn number_of_ways(n: i32, x: i32, y: i32) -> i32 {
        let n = n as usize;
        let x = x as usize;
        let y = y as i64;
        let maxv = n.max(x);
        let mut fact = vec![1i64; maxv+2];
        let mut invf = vec![1i64; maxv+2];
        let MOD = 1_000_000_007i64;
        for i in 1..fact.len() {
            fact[i] = fact[i-1] * i as i64 % MOD;
        }
        invf[maxv+1] = powmod(fact[maxv+1], MOD-2, MOD);
        for i in (0..=maxv).rev() {
            invf[i] = invf[i+1] * (i as i64 + 1) % MOD;
        }
        let perm = |a: usize, b: usize| -> i64 {
            if b > a { 0 } else { fact[a] * invf[a-b] % MOD }
        };
        let mut S = vec![vec![0i64; x+1]; n+1];
        S[0][0] = 1;
        for i in 1..=n {
            for j in 1..=x {
                S[i][j] = (S[i-1][j-1] + S[i-1][j] * j as i64) % MOD;
            }
        }
        let mut ans = 0i64;
        for k in 1..=n.min(x) {
            let ways = S[n][k] * perm(x, k) % MOD;
            let score = powmod(y, k as i64, MOD);
            ans = (ans + ways * score % MOD) % MOD;
        }
        ans as i32
    }
}
fn powmod(mut a: i64, mut b: i64, m: i64) -> i64 {
    let mut res = 1;
    while b > 0 {
        if b & 1 == 1 {
            res = res * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution {
    numberOfWays(n: number, x: number, y: number): number {
        const MOD = 1e9 + 7;
        const maxv = Math.max(n, x);
        const fact = Array(maxv+2).fill(1);
        const invf = Array(maxv+2).fill(1);
        for (let i = 1; i < fact.length; ++i) fact[i] = fact[i-1] * i % MOD;
        invf[maxv+1] = powmod(fact[maxv+1], MOD-2, MOD);
        for (let i = maxv; i >= 0; --i) invf[i] = invf[i+1] * (i+1) % MOD;
        const perm = (a: number, b: number) => b > a ? 0 : fact[a] * invf[a-b] % MOD;
        const S = Array.from({length: n+1}, () => Array(x+1).fill(0));
        S[0][0] = 1;
        for (let i = 1; i <= n; ++i) {
            for (let j = 1; j <= x; ++j) {
                S[i][j] = (S[i-1][j-1] + S[i-1][j] * j) % MOD;
            }
        }
        let ans = 0;
        for (let k = 1; k <= Math.min(n, x); ++k) {
            const ways = S[n][k] * perm(x, k) % MOD;
            const score = powmod(y, k, MOD);
            ans = (ans + ways * score % MOD) % MOD;
        }
        return ans;
    }
}
function powmod(a: number, b: number, mod: number): number {
    let res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

Complexity

⏰ Time complexity: O(n * x + max(n, x)), for computing Stirling numbers and factorials.
🧺 Space complexity: O(n * x), for the DP table of Stirling numbers.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Stars and Bars with Power for Band Scores#

Intuition#

Approach#

Code#

Complexity#