(LeetCode 每日一题) 3405. 统计恰好有 K 个相等相邻元素的数组数目(组合数学、快速幂)

题目：3405. 统计恰好有 K 个相等相邻元素的数组数目

思路：数组长度为n，那么最多有n-1个相邻元素相同，答案是满足k个相邻元素相同，即有n-1-k个相邻元素不同。
等价于，在数组的缝隙(n-1个缝隙)里插入n-1-k个隔板，分成n-1-k+1=n-k个子数组。
即组合数：C(n-1,n-1-k)=C(n-1,k)
第一个子数组有m个选法，第二个及后面的都有m-1个选法。最后答案如下：

大佬思路

C++版本：

class Solution {
public:
    // n个 -> n-1 -> k -> n-1-k个不同的
    // n-1 -> n-1-k
    // C(n-1,n-1-k)*m*(m-1)^(n-1-k)

    const int mod=1e9+7;
    typedef long long LL;
    LL qmi(LL u,int q){
        LL res=1;
        while(q){
            if(q&1){
                res=(res*u)%mod;
            }
            q>>=1;
            u=((LL)u*u)%mod;
        }
        return res;
    }

    LL C(int a,int b){
        LL res=1;
        for(int i=0;i<b;i++){
            res=(res*(a-i))%mod;
            res=(res*qmi(i+1,mod-2))%mod;
        }
        return res;
    }

    int countGoodArrays(int n, int m, int k) {
        return C(n-1,n-1-k)*m%mod*qmi(m-1,n-1-k)%mod;
    }
};

JAVA版本：

class Solution {

    static final int mod=1_000_000_007;
    long qmi(long u,int q){
        long res=1;
        while(q!=0){
            if((q&1)==1){
                res=(res*u)%mod;
            }
            q>>=1;
            u=((long)u*u)%mod;
        }
        return res;
    }

    long C(int a,int b){
        long res=1;
        for(int i=0;i<b;i++){
            res=(res*(a-i))%mod;
            res=(res*qmi(i+1,mod-2))%mod;
        }
        return res;
    }

    public int countGoodArrays(int n, int m, int k) {
        return (int)(C(n-1,n-1-k)*m % mod*qmi(m-1,n-1-k) % mod);
    }
}

Go版本：

const mod=1_000_000_007


func countGoodArrays(n int, m int, k int) int {
    return C(n-1,n-1-k)*m%mod*qmi(m-1,n-1-k)%mod
}

func C(a int,b int) int {
    res:=1
    for i:=0;i<b;i++ {
        res=(res*(a-i))%mod
    }
    for i:=1;i<=b;i++ {
        res=(res*qmi(i,mod-2))%mod
    }
    return res
}
func qmi(a int,p int) int {
    res:=1
    for p!=0 {
        if (p&1)==1 {
            res=(res*a)%mod
        }
        p>>=1
        a=(a*a)%mod
    }
    return res
}