2021-04-05

题目描述
我们有n个空盒子，所以让我们用m种颜色重新着色那些盒子。
盒子排成一行。不允许用相同的颜色给任何相邻的盒子上色。框i和框i + 1表示每隔i，1≤i≤n相邻。
我们还希望n个框的不同颜色的总数恰好是k。
当且仅当至少一个盒子用不同颜色上色时，两种方法才被认为是不同的。

对于恰好这个词,在开始还是不太清楚,学习了一段时间之后,对于此有了自己的理解,恰好需要用至少或者不超过来运用容斥原理进行表示。
分析题目..
1.首先需要进行选择颜色种类C(m, k)种选法
2.我们可以假定当前我们有i种颜色可以使用,对当前的j位置进行上***r> 想一下,我们可以知道对于j位置来说,它只会对旁边两个位置产生影响,所以当前j位置有i种选法,那么其它位置就有i-1种选法,那么就是i(i-1)^(n-1);
3.由题目的描述中的恰好在此题目中,需要理解为不超过k种颜色的容斥原理进行求解。
由上面的三点我们可以得到答案
ans = C(m,k)(C(k,k)k(k-1)^(n-1) - C(k,k-1)(k-i)(k-2)^(n-1)) + ........
**求解C（m,k）,由于m是属于(1,1e9)那么就不能用预处理数组进行求解,可以利用自己喜欢的方式进行求解~~

#include<bits/stdc++.h>
#define ll long long
#define pr printf
#define sc scanf
using namespace std;
const int maxn = 1e6 + 10;

const int mod = 1e9 + 7;
ll fact[maxn],infact[maxn];
ll qpow(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b & 1)ans = ans*a%mod;
        b >>= 1;
        a = a*a%mod;
    }
    return ans;
}
ll inv(ll a){
    return qpow(a,mod-2)%mod;
}
ll C(ll a, ll b){
    if(b > a || a < 0 || b < 0)return 0;
    if(b == 0 || b == a)return 1;
    return fact[a]*infact[b]%mod*infact[a-b]%mod;
}
void init() {
    fact[0] = 1;
    for (int i = 1; i < maxn; i++) {
        fact[i] = fact[i - 1] * i % mod;
    }
    infact[maxn - 1] = qpow(fact[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--) {
        infact[i] = infact[i + 1] * (i + 1) % mod;
    }
}

int main() {
    init();
    int T;
    sc("%d", &T);
    while (T--) {
        ll n, m, k, ans = 0;
        sc("%lld%lld%lld", &n, &m, &k);
        for (int i = 0, cur = 1; i < k; i++, cur = -cur)
            ans = (ans + cur * C(k, k - i) * (k - i) % mod * qpow(k - i - 1, n - 1) % mod + mod) % mod;
        for (int i = 0; i < k; i++)
            ans = ans * (m - i) % mod * inv(k - i) % mod;
        cout << ans << endl;
    }
    return 0;
}