[每日一题] [NC13884] Paint Box

题目大意：有n个盒子，总共有m中可能颜色，问有多少种染色方式，使得相邻的盒子不相邻，且恰好有k中颜色。数据范围n和m都非常大，k不超过1E6。

https://ac.nowcoder.com/acm/problem/13884

如果n和m的范围不大，这题可以用一个DP来完成，即考虑前i个盒子恰好k种颜色的染发。那么(i,k)来自(i-1,k)并且选择这k种颜色中不是i-1的颜色的一种，有k-1种选法；或来自(i-1,k-1)并且选择剩下的m-(k-1)种颜色中的一种，有m-k+1种选法。时间复杂度为O(n*k)。

但是这道题显然要求更快，那么首先想到可以不妨假设选到的k种颜色就是1,2,...,k。那么答案就是这个数字乘以choose(m,k)。接下来就是如何计算恰好选满1,2,...,k的选法。

我们首先考虑只能从1,2,...,s种选择的染色方案数，乘法原理，第一个数字有s种选法，剩下的每次都有(s-1)种选法，即。那么能否利用这一结论计算总数呢？只要使用容斥原理即可：首先算出只能从1,2,...,k的方案数，减去1,2,...,(k-1)的方案数，1,2,...,(k-1),k的方案数，等等；加上所有k-2个的方案数；减去所有k-3的方案数；...。其中s个的方案数就是。

需要注意的几个点就是choose的计算，这里可以使用基于快速幂的inversion，还有就是可以直接使用快速幂。有一个容易出错的地方是用容斥原理减的时候要防止算出负数，这里可以特别当心一点，我用了一个临时变量算乘法，然后取模，不然会出现负数，总之C++要非常当心这种mod下的乘法。Debug的时候用了DP对拍很有效，找到了很多bug。

ll n, m, k;
ll power(ll x, ll k) {
  ll ret = 1LL;
  while(k) {
    if(k & 1LL) {
      ret *= x;
      ret %= MOD;
    }
    k >>= 1;
    x *= x;
    x %= MOD;
  }
  return ret;
}
ll inv(ll x) {
  return power(x,MOD-2);
}
ll choose(ll m, ll k) {
  ll ans = 1;
  REP(i, k) {
    ans *= m - i;
    ans %= MOD;
    ans *= inv(i + 1);
    ans %= MOD;
  }
  return ans;
}
ll doit() {
  ll mult = choose(m, k);
  // cerr << "choose" << m << ", " << k << ":" << mult << endl;
  ll ans = 0;
  ll sign = 1;
  ll choices = 1;
  for (int c = k; c >= 1; --c) {
    ll pw = c;
    pw *= power(c - 1, n - 1);
    pw %= MOD;
    // cerr << "choices: " << choices << endl;
    // cerr << "pw: " << pw << endl;
    ll tmp = choices * pw;
    tmp %= MOD;
    if (sign == 1) {
      ans += tmp;
    } else {
      ans += MOD - tmp;
    }
    ans %= MOD;
    sign = -sign;
    choices *= c;
    choices %= MOD;
    choices *= inv(k - c + 1);
    choices %= MOD;
  }
  mult *= ans;
  mult %= MOD;
  return mult;
}
int main(int argc, char* argv[]) {
  FET(t){
    read(n,m,k);
    print(doit());
  }
  return 0;
}