Welcome to Subscribe On Youtube
3405. Count the Number of Arrays with K Matching Adjacent Elements
Description
You are given three integers n
, m
, k
. A good array arr
of size n
is defined as follows:
- Each element in
arr
is in the inclusive range[1, m]
. - Exactly
k
indicesi
(where1 <= i < n
) satisfy the conditionarr[i - 1] == arr[i]
.
Return the number of good arrays that can be formed.
Since the answer may be very large, return it modulo 109 + 7
.
Example 1:
Input: n = 3, m = 2, k = 1
Output: 4
Explanation:
- There are 4 good arrays. They are
[1, 1, 2]
,[1, 2, 2]
,[2, 1, 1]
and[2, 2, 1]
. - Hence, the answer is 4.
Example 2:
Input: n = 4, m = 2, k = 2
Output: 6
Explanation:
- The good arrays are
[1, 1, 1, 2]
,[1, 1, 2, 2]
,[1, 2, 2, 2]
,[2, 1, 1, 1]
,[2, 2, 1, 1]
and[2, 2, 2, 1]
. - Hence, the answer is 6.
Example 3:
Input: n = 5, m = 2, k = 0
Output: 2
Explanation:
- The good arrays are
[1, 2, 1, 2, 1]
and[2, 1, 2, 1, 2]
. Hence, the answer is 2.
Constraints:
1 <= n <= 105
1 <= m <= 105
0 <= k <= n - 1
Solutions
Solution 1
-
class Solution { private static final int N = (int) 1e5 + 10; private static final int MOD = (int) 1e9 + 7; private static final long[] f = new long[N]; private static final long[] g = new long[N]; static { f[0] = 1; g[0] = 1; for (int i = 1; i < N; ++i) { f[i] = f[i - 1] * i % MOD; g[i] = qpow(f[i], MOD - 2); } } public static long qpow(long a, int k) { long res = 1; while (k != 0) { if ((k & 1) == 1) { res = res * a % MOD; } k >>= 1; a = a * a % MOD; } return res; } public static long comb(int m, int n) { return (int) f[m] * g[n] % MOD * g[m - n] % MOD; } public int countGoodArrays(int n, int m, int k) { return (int) (comb(n - 1, k) * m % MOD * qpow(m - 1, n - k - 1) % MOD); } }
-
const int MX = 1e5 + 10; const int MOD = 1e9 + 7; long long f[MX]; long long g[MX]; long long qpow(long a, int k) { long res = 1; while (k != 0) { if ((k & 1) == 1) { res = res * a % MOD; } k >>= 1; a = a * a % MOD; } return res; } int init = []() { f[0] = g[0] = 1; for (int i = 1; i < MX; ++i) { f[i] = f[i - 1] * i % MOD; g[i] = qpow(f[i], MOD - 2); } return 0; }(); long long comb(int m, int n) { return f[m] * g[n] % MOD * g[m - n] % MOD; } class Solution { public: int countGoodArrays(int n, int m, int k) { return comb(n - 1, k) * m % MOD * qpow(m - 1, n - k - 1) % MOD; } };
-
mx = 10**5 + 10 mod = 10**9 + 7 f = [1] + [0] * mx g = [1] + [0] * mx for i in range(1, mx): f[i] = f[i - 1] * i % mod g[i] = pow(f[i], mod - 2, mod) def comb(m: int, n: int) -> int: return f[m] * g[n] * g[m - n] % mod class Solution: def countGoodArrays(self, n: int, m: int, k: int) -> int: return comb(n - 1, k) * m * pow(m - 1, n - k - 1, mod) % mod
-
const MX = 1e5 + 10 const MOD = 1e9 + 7 var f [MX]int64 var g [MX]int64 func qpow(a int64, k int) int64 { res := int64(1) for k != 0 { if k&1 == 1 { res = res * a % MOD } a = a * a % MOD k >>= 1 } return res } func init() { f[0], g[0] = 1, 1 for i := 1; i < MX; i++ { f[i] = f[i-1] * int64(i) % MOD g[i] = qpow(f[i], MOD-2) } } func comb(m, n int) int64 { return f[m] * g[n] % MOD * g[m-n] % MOD } func countGoodArrays(n int, m int, k int) int { ans := comb(n-1, k) * int64(m) % MOD * qpow(int64(m-1), n-k-1) % MOD return int(ans) }
-
const MX = 1e5 + 10; const MOD = BigInt(1e9 + 7); const f: bigint[] = Array(MX).fill(1n); const g: bigint[] = Array(MX).fill(1n); function qpow(a: bigint, k: number): bigint { let res = 1n; while (k !== 0) { if ((k & 1) === 1) { res = (res * a) % MOD; } a = (a * a) % MOD; k >>= 1; } return res; } (function init() { for (let i = 1; i < MX; ++i) { f[i] = (f[i - 1] * BigInt(i)) % MOD; g[i] = qpow(f[i], Number(MOD - 2n)); } })(); function comb(m: number, n: number): bigint { return (((f[m] * g[n]) % MOD) * g[m - n]) % MOD; } export function countGoodArrays(n: number, m: number, k: number): number { const ans = (((comb(n - 1, k) * BigInt(m)) % MOD) * qpow(BigInt(m - 1), n - k - 1)) % MOD; return Number(ans); }
-
impl Solution { pub fn count_good_arrays(n: i32, m: i32, k: i32) -> i32 { const N: usize = 1e5 as usize + 10; const MOD: i64 = 1_000_000_007; use std::sync::OnceLock; static F: OnceLock<Vec<i64>> = OnceLock::new(); static G: OnceLock<Vec<i64>> = OnceLock::new(); fn qpow(mut a: i64, mut k: i64, m: i64) -> i64 { let mut res = 1; while k != 0 { if k & 1 == 1 { res = res * a % m; } a = a * a % m; k >>= 1; } res } fn init() -> (&'static Vec<i64>, &'static Vec<i64>) { F.get_or_init(|| { let mut f = vec![1i64; N]; for i in 1..N { f[i] = f[i - 1] * i as i64 % MOD; } f }); G.get_or_init(|| { let f = F.get().unwrap(); let mut g = vec![1i64; N]; for i in 1..N { g[i] = qpow(f[i], MOD - 2, MOD); } g }); (F.get().unwrap(), G.get().unwrap()) } fn comb(f: &[i64], g: &[i64], m: usize, n: usize) -> i64 { f[m] * g[n] % MOD * g[m - n] % MOD } let (f, g) = init(); let n = n as usize; let m = m as i64; let k = k as usize; let c = comb(f, g, n - 1, k); let pow = qpow(m - 1, (n - 1 - k) as i64, MOD); (c * m % MOD * pow % MOD) as i32 } }