Find the number of possible ways for an event

Math Dynamic Programming Combinatorics

34.9% acceptance

Feb 23, 2026

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_ways(n: i32, x: i32, y: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as usize;
    let x = x as usize;
    let y = y as i64;
    
    // Number of ways to assign n performers to x stages where each band is non-empty (Stirling 2nd kind * x! / (x-k)! for exactly k stages)
    // But some stages can be empty.
    // Total ways = sum over k=1 to min(n,x) of: 
    //   S(n, k) * C(x, k) * k! (surjective assignments to exactly k stages) * y^k (score for each band)
    // where S(n,k) is Stirling number of second kind
    // Wait: assign to stages where order matters (stage 1, stage 2, ..., stage x are distinct)
    // Number of ways to assign n performers to exactly k out of x stages:
    //   C(x,k) * k! * S(n,k) [choose k stages, arrange them, partition performers]
    //   = x! / (x-k)! * S(n,k)
    // Score for k non-empty stages: y^k
    
    // Precompute Stirling numbers S(n, k) for k=0..n
    let mut stirling = vec![vec![0i64; n + 1]; n + 1];
    stirling[0][0] = 1;
    for i in 1..=n {
      for k in 1..=i {
        stirling[i][k] = (k as i64 * stirling[i-1][k] + stirling[i-1][k-1]) % MOD;
      }
    }
    
    // Compute falling factorial x * (x-1) * ... * (x-k+1)
    let mut result = 0i64;
    let mut falling = 1i64;
    let mut y_pow = 1i64;
    for k in 1..=x.min(n) {
      falling = falling * ((x - k + 1) as i64) % MOD;
      y_pow = y_pow * y % MOD;
      let ways = falling * stirling[n][k] % MOD * y_pow % MOD;
      result = (result + ways) % MOD;
    }
    
    result as i32
  }
}