atcoder abc167-E

题目大意：用M种颜色给N个排成一排的方块涂色，要求至多有K个相邻方块同色的方案书。
思路: 纯粹数学知识。第一步，考虑如何选k个方块（准备让它们同色），不妨这样想：N个方块排成一排，中间有N-1个空，我们从N-1空中选k个，每个空左右两边方块同色，则有_N-1C_k种方法；
第二步，考虑涂色，第一个显然M种方法，第二个M-1，。。。，故M(M-1)^N-k-1。
所以，最后答案=_N-1C_k * M(M-1)^N-k-1

因为快速幂易求(M-1)^N-k-1，现在剩下怎么求_N-1C_k？_n-1C_k = = ，分子递推易求，因为这个结果肯定要模p，给定的p是质数，可以用逆元把除变成乘，根据费马小定理k^-1=k^p-2(mod p)，(k!)^-1 = 1^-12^-1...*k^-1。
反思：需要补一些数论知识：模的逆、逆的求法等，详见：
代码:

#include<bits/stdc++.h>
using namespace std;
#define LL  long long
#define MOD  998244353

LL N, M, K;

LL qpow(LL base, LL pow) {
    return pow?((pow&1?base:1)*qpow(base*base%MOD, pow/2))%MOD:1;
}
int main() {
    cin >> N >> M >>K;
    LL ans = 0;
    LL temp = 1;
    for(int k=0; k<=K; k++) {
        ans += ((M * temp)%MOD * qpow(M-1, N-1-k))%MOD;
        ans %= MOD;
        temp = (temp * (N-k-1))%MOD * qpow(k+1, MOD-2);
        temp %= MOD;
    }
    cout << ans << endl;
    return 0;
}