Combinations k equal siblings 1..m in [n] array #hard #combinatorics #math
Intuition
Didn't solve. Some thougths:
// n = 4, m = 2, k = 2
// [1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], [2, 1, 1, 1], [2, 2, 1, 1] [2, 2, 2, 1]
// dp[i] = (1..m).sum { a (1..m).sum { b (a == b) + dp[i + 2] } }
// 10^5 x 10^5 will give TLE/MLE
// combinatorics? all perimutations excluding the banned
// 1 1 2 1 2 2 2 1 1 2 2 1 k = 1
// 1 2 1 2 1 2 k = 0 ban
// 1 1 1 2 2 2 k = 2 ban
// k max = n - 1
// (0..kMax) = all perm "111".toString(2)
// stil don't know how to count perm for each `k`
// hints are pointing to the DP, but how it is not TLE?
// (26 minute, give up, its combinatorics)
// m * C(n - 1, k) * (m - 1) ** (n - 1 - k)
If I understood it right:
stars and bars: the bars are equal parts, we have k of them on n-1 positions: C(n-1,k)
first is 1..m
the stars can be 1..m - 1(prev) at (n-1) - k positions (after bars are placed): (m-1)^(n-1-k)
Approach
this time I recognized my inability to solve combinatorics much faster than 1 hour (26 minute gave up)
memoize a^b % m: it is derived from math a ^ b = (a^2)^(b/2) * a^(b%2), b /= 2, a = a * a
of course it is impossible for me to solve without some huge investment into combinatorics theory, but some tricks are worth to learn
Complexity
Time complexity: $$O(nlogn)$$
Space complexity: $$O(1)$$
Code
// 28ms
fun countGoodArrays(n: Int, m: Int, k: Int): Int {
val M = 1_000_000_007; val m = 1L * m; var nCr = 1L; var den = 1L
fun pow(a: Long, b: Int): Long =
if (b == 0) 1L else (pow((a * a) % M, b / 2) * if (b % 2 > 0) a else 1) % M
for (i in 1..k) { nCr = (nCr * (n - i)) % M; den = (den * i) % M }
nCr = (nCr * pow(den, M - 2)) % M
return ((((m * nCr) % M) * pow(m - 1, n - k - 1)) % M).toInt()
}
// 28ms
pub fn count_good_arrays(n: i32, m: i32, k: i32) -> i32 {
let (M, n, m, k, mut nCr, mut den) = (1_000_000_007, n as i64, m as i64, k as i64, 1, 1);
fn pow(a: i64, b: i64, M: i64) -> i64 {
if b == 0 { 1 } else { (pow((a * a) % M, b / 2, M) * if (b % 2 > 0) { a } else { 1 }) % M }
}
for i in 1..=k { nCr = (nCr * (n - i)) % M; den = (den * i) % M }
nCr = (nCr * pow(den, M - 2, M)) % M;
((((m * nCr) % M) * pow(m - 1, n - k - 1, M)) % M) as i32
}
// 25ms
#define M 1000000007
int countGoodArrays(int n, int m, int k) {
auto p = [](long a, long b) {
long r = 1;
while (b) { if (b & 1) r = r * a % M; a = a * a % M; b >>= 1; }
return r;
};
long x = 1, y = 1;
for (int i = 1; i <= k; ++i) { x = x * (n - i) % M; y = y * i % M; }
return x * p(y, M - 2) % M * m % M * p(m - 1, n - k - 1) % M;
}
