Find the Number of Possible Ways for an Event

We can solve this problem using dynamic programming. We build a solution for n performers based on the solution for n-1 performers. Let dp[i][j] be the number of ways to assign i performers to x stages such that exactly j stages are occupied. We can derive a recurrence relation for dp[i][j]. The final answer is obtained by summing up the ways for all possible numbers of occupied stages, each weighted by the number of ways to assign scores.

• Let dp[i][j] be the number of ways to assign i performers to x stages, resulting in exactly j occupied stages.
• The recurrence relation is dp[i][j] = (dp[i-1][j] * j + dp[i-1][j-1] * (x - j + 1)) % MOD.
• The base case is dp[0][0] = 1.
• We can use a 1D array dp of size x+1 to optimize space. dp[j] will store the number of ways to assign the current number of performers to occupy j stages.
• The algorithm proceeds as follows:
  1. Initialize a 1D array dp of size x+1, with dp[0] = 1.
  2. Loop for i from 1 to n (performers).
  3. In an inner loop, update dp[j] for j from min(i, x) down to 1 using the recurrence.
  4. After the loops, dp[j] contains the number of ways to assign n performers to occupy j stages.
  5. The total number of ways is the sum of dp[j] * y^j for j from 1 to min(n, x).
  6. A modular exponentiation function is needed to compute y^j.

Let dp[i][j] be the number of ways to assign i performers to x stages, resulting in exactly j occupied stages. To compute dp[i][j], we consider the i-th performer. This performer can either be assigned to one of the j stages already occupied by the first i-1 performers, or to one of the x-(j-1) empty stages.

This leads to the recurrence: dp[i][j] = dp[i-1][j] * j + dp[i-1][j-1] * (x - j + 1).

The base case is dp[0][0] = 1 (0 performers, 0 occupied stages, 1 way).

We can build a DP table of size (n+1) x (min(n, x)+1). After computing dp[n][j] for all j from 1 to min(n, x), we can find the total number of ways. For a fixed j, there are dp[n][j] ways to form j bands. Each of these j bands can be awarded a score from 1 to y, giving y^j ways to assign scores.

The total number of ways is sum_{j=1 to min(n, x)} (dp[n][j] * y^j).

All calculations should be done modulo 10^9 + 7. The space complexity can be optimized from O(n*x) to O(x) by noticing that dp[i] only depends on dp[i-1], allowing for an in-place update.

class Solution {
    long MOD = 1_000_000_007;

    public int numberOfWays(int n, int x, int y) {
        long[] dp = new long[x + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = Math.min(i, x); j >= 1; j--) {
                long term1 = (dp[j] * j) % MOD;
                long term2 = (dp[j - 1] * (x - j + 1)) % MOD;
                dp[j] = (term1 + term2) % MOD;
            }
        }

        long totalWays = 0;
        for (int j = 1; j <= Math.min(n, x); j++) {
            long waysForJStages = dp[j];
            long scoreWays = power(y, j);
            totalWays = (totalWays + (waysForJStages * scoreWays) % MOD) % MOD;
        }

        return (int) totalWays;
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}