Readme

3405.Count-the-Number-of-Arrays-with-K-Matching-Adjacent-Elements

考虑到恰有k个位置的元素与其左边元素相同，那么将其与其左边元素“合并”后，数组里可看做只有n-k个元素，并且这些元素在相邻的位置上不重复。证明很显然，如果“合并”后依然存在相邻的相同元素，那么原数组里必然不止k处相邻的相同元素。

从原数组里挑出k个位置，有comb(n,k)种方案。

任何一种上述的方案，对于“合并”后的数组的n-k个元素，要求相邻之间不重复，有多少种方案？第一个位置有m种选择，之后每一个位置都只有m-1种选择。故总共有m*m^(n-k-1)种方案。

所以最终答案就是简单的数学表达式 comb(n,k)*m*m^(n-k-1).

因为n和k是1e5，所以不能用o(n*k)的复杂度计算组合数任何n以内的组合数。我们可以直接硬算comb(n,k) = n!/k!/(n-k)!. 其中阶乘的复杂度就是o(n)，但是涉及到了除法，故需要介入逆元。逆元的计算公式是inv_x = quickPow(x, (MOD-2)).