题解 | #Paint Box#

Paint Box

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

定义用不超过 $k$ 种颜色涂完 $n$ 个盒子的方案数为 $x_k=k(k-1)^{n-1}$ 。

意为：第一个盒子有 $k$ 种选法，第二个之后的每一个盒子都需要和前一个不一样即为 $k-1$ 种选法，共选了 $n-1$ 次。

于是，根据容斥原理，用正好 $k$ 种颜色涂完 $n$ 个盒子的方案数为： $tmp = x_k - C_{k}^{k-1}x_{k-1}+C_{k}^{k-2}x_{k-2}+...+(-1)^{k}x_1$

对于对于选中的k-1 种颜色的集合 s1 和 s2 (其中 s1 和 s2 只有一种颜色不一样) 对于集合相同部分会被减去两次也就是（k-2）种颜色的方案所以要。

题中给了 $m$ 种颜色，从 $m$ 种颜色选 k 种的方案数为 $C_{m}^{k}$ 。

题目中要求的 n 个盒子，用 m 种颜色中选出正好 k 种颜色，且相邻盒子颜色不同的方案数为： $ans=C_{m}^{k}tmp=C_{m}^{k}x_k-C_{m}^{k-1}x_{k-1}+C_{m}^{k-2}x_{k-2}+...+(-1)^{k}x_1$
于是，设 $y_k=C_m^kx_k=C_m^kk(k-1)^{n-1}$
则有： $ans=y_k-y_{k-1}+y_{k-2}-...$

注意，在这里， $y_k$ 并不代表数学上的含义，而是找到了一个利于计算的通式
先看特殊值
n=m=k=4，ans=24
n=m=k=5，ans=120
n=m=k 时，ans = k!
m=k>n时，ans=0
这些可以作为编程时的边界条件
考虑到n，m，k的数值，需要用到快速幂与逆元与组合数公式运算

注意到 $C_m^k$ 中的 $m$ 和 $k$ 的值，是不能直接用 O(1) 时间进行代入计算的。于是，可以考虑打表，题解链接：
https://blog.csdn.net/haut_ykc/article/details/78067469

但是，我们退回来想，利用式子 $ans=C_{m}^{k}tmp$ 呢？ $C_m^k$ 可以利用公式 $C_m^k=\frac {m!} {k!(m-k)!} = \frac {(m-k+1)(m-k+2)...m} {(k)(k-1)...1}$
即第一部分可以在O(k)的时间复杂度，利用阶乘和逆元的阶乘得到
第二部分可以利用阶乘、逆元和逆元的阶乘得到，题解链接：

https://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/104188313

#include<stdio.h>
#include<cstdio>
#include<iostream>
using namespace std;

#define ll long long

const ll mod=1e9+7;
const int maxn=1e6+10;

int T;
ll p[maxn], invp[maxn], inv[maxn];

//(a^b)%p
ll qp(ll a, ll b){
    a %= mod;
    ll ret = 1;
    while(b){
        if (b & 1)
            ret = ret * a % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}

void init(){
    p[0] = 1;
    for(int i = 1; i <= 1000000; i++)
        p[i] = p[i - 1] * i % mod;
    invp[1000000] = qp(p[1000000], mod - 2);
    for(int i = 1000000 - 1; i>=0; i--)
        invp[i] = invp[i + 1] * (i + 1) % mod;
    inv[1] = 1;
    for(int i = 2; i <= 1000000; i++)
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
}

ll C(ll n, ll m){
    return p[n] * invp[m] % mod * in*** - m] % mod;
}

int main()
{
    init();
    scanf("%d",&T);
    while(T--)
    {
        ll n,m,k;
        scanf("%lld%lld%lld",&n,&m,&k);
        ll Cmk = 1;
        for(int i=1; i<=k; i++)
            Cmk = Cmk * (m - k + i) % mod * inv[i] % mod;
        ll tmp = 0;
        for(int i=0; i<k; i++)
            if (i % 2 == 0)
                tmp = (tmp + C(k, k-i) * (k - i) % mod * qp(k - i - 1, n - 1) % mod + mod) % mod;
            else
                tmp = (tmp - C(k, k-i) * (k - i) % mod * qp(k - i - 1, n - 1) % mod + mod) % mod;
        ll ans = Cmk * tmp % mod;
        printf("%lld\n", ans);
    }
    return 0;
}