Find the number of k even arrays

Dynamic Programming

61.4% acceptance

Mar 31, 2026

You are given three integers n, m, and k. An array arr is called k-even if there are exactly k indices such that, for each of these indices i (0 <= i < n - 1): (arr[i] * arr[i + 1]) - arr[i] - arr[i + 1] is even. Return the number of possible k-even arrays of size n where all elements are in the range [1, m]. Since the answer may be very large, return it modulo 109 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count_of_arrays(n: i32, m: i32, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as usize;
    let k = k as usize;
    let m = m as i64;
    let even = m / 2; // count of even numbers in [1,m]
    let odd = m - even; // count of odd numbers in [1,m]
    // (a*b) - a - b = a*b - a - b = (a-1)*(b-1) - 1, which is even iff (a-1)*(b-1) is odd,
    // meaning both a and b are even.
    // dp[j] = number of arrays of length i with exactly j "k-even" pairs
    // Transition: if we append an even number after an even number, j increases by 1
    // if we append anything else, j stays the same
    // State: (length, count of k-even pairs, last parity)
    // dp[j][0] = ends with odd, dp[j][1] = ends with even
    let mut dp = vec![vec![0i64; 2]; k + 2];
    dp[0][0] = odd;
    dp[0][1] = even;
    for _ in 1..n {
      let mut ndp = vec![vec![0i64; 2]; k + 2];
      for j in 0..=k {
        // ends odd -> append odd: stays j, ends odd
        // ends odd -> append even: stays j, ends even
        ndp[j][0] = (ndp[j][0] + dp[j][0] % MOD * odd % MOD) % MOD;
        ndp[j][1] = (ndp[j][1] + dp[j][0] % MOD * even % MOD) % MOD;
        // ends even -> append odd: stays j, ends odd
        ndp[j][0] = (ndp[j][0] + dp[j][1] % MOD * odd % MOD) % MOD;
        // ends even -> append even: j+1, ends even
        if j + 1 <= k {
          ndp[j + 1][1] = (ndp[j + 1][1] + dp[j][1] % MOD * even % MOD) % MOD;
        }
      }
      dp = ndp;
    }
    ((dp[k][0] + dp[k][1]) % MOD) as i32
  }
}