Leetcode-3405-Count-the-Number-of-Arrays-with-K-matching-Adjacent-Elements

题目大意：输入是三个数字，，。一个长度为的good array有以下限制：数组中的每个元素的范围都为$[1, m]$；正好有$k$个$i$满足$arr[i-1] == arr[i]$。输出是满足条件的good array的数量。因为数量可能很多，所以对结果取模1e9+7。

很容易想到dp，将状态$dp[i][j]$定义为当前arr的长度为，恰好有个$k$满足$arr[k-1] == arr[k]$。那么装转方程应为$dp[i][j] = dp[i-1][j-1] + dp[i-1][j] * (m-1)$。看下数据范围$1<=n，m<=5*10^4$，时间复杂度$O(n^2)$的话是必TLE的。

于是想到了组合数学的解法，首先是第个元素可以有种选择；然后在剩下个元素中选取个位置；也就是说这k个位置外加第个位置不用再考虑赋值了，剩下的个位置不能跟前一个相同。算式可以得到$m*C_{n-1}^{k}*(m-1)^{n-1-k}$。

按照公式交了一发WA，但是实际上已经过了很多样例了，感觉和取模有关。查了一下取模只有乘法分配律没有除法分配律。因为在算$C_{n-1}^{k}$的时候有用到除法，所以出错了。这种情况需要用到扩展欧几里得或者费马小定理来求除数在mod下的乘法逆元，然后用乘法逆元代替除法。看了一下利用二项式展开证明费马小定理的原理。然后实现的时候用快速幂降了一下复杂度到$log(n)$，不然用朴素的暴力1e9+7次循环八成还是会TLE的。

class Solution {
public:
    int mod = 1e9 + 7;

    long long modPow(long long base, long long exp, int mod) {
        long long result = 1;
        while (exp > 0) {
            if (exp % 2) result = result * base % mod;
            base = base * base % mod;
            exp /= 2;
        }
        return result;
    }

    long long modInverse(long long a, int mod) {
        return modPow(a, mod - 2, mod);
    }

    int countGoodArrays(int n, int m, int k) {
        long long ans = m, res = 1;

        for (int i = n - 1; i >= n - k; i--) {
            ans = ans * i % mod;
        }

        for (int i = 1; i <= k; i++) {
            res = res * i % mod;
        }

        ans = ans * modInverse(res, mod) % mod;

        for (int i = 0; i < (n - 1 - k); i++) {
            ans = ans * (m - 1) % mod;
        }

        return (int)ans;
    }
};

这题公式推出来之后，写法上就挺套路的。需要快速幂和乘法逆元的知识。