题解 | #Paint Box#

• 快速幂
• 排列组合
• 容斥原理及二项式反演
• 题解

快速幂

对于一个数的次幂，如:$2^{10}2^\{10\}$。最常规的计算方法是将2乘以10次，时间复杂度为：O($NN$)。
如果我们将它写成二进制:$2^{{1010}_2}2^\{\{1010\}\_2\}$，很自然的可以分解成$2^{{1000}_2}2^\{\{1000\}\_2\}$与$2^{{10}_2}2^\{\{10\}\_2\}$两个数相乘，即：$2^8\ast 2^{2}2^\{8\}*2^\{2\}$。这样，我们可以在计算$2^{8}2^8$时使用已经计算完毕的$2^{4}2^4$，所以我们只需要将底数不断的平方就可以计算出答案，时间复杂度:O($lo{g}_{2}Nlog\_2N$)。

long long qpow(long long n, long long m)
{
    long long ans = 1;
    while (m)
    {
        if (m & 1)
            ans *= n;
        n *= n;
        m >>= 1;
    }
    return ans;
}

排列组合

1.逆元

自然数a,p互质，如果满足a*b%p=1，那么b为a%p的逆元

2.小费马定理

公式：a与p互质，$a^{p-1}\mathrm{\%}p=1a^\{p-1\}\backslash \%p=1$
证明：
1.如果自然数c和p互质，$a\ast c\mathrm{\%}p=b\ast c\mathrm{\%}pa*c\backslash \%p=b*c\backslash \%p$,那么我们可以得到$a\mathrm{\%}p=b\mathrm{\%}pa\backslash \%p=b\backslash \%p$
设$a=l\ast p+qa=l*p+q$， $b=r\ast p+qb=r*p+q$ $\Rightarrow \backslash Rightarrow$ $a\mathrm{\%}p=b\mathrm{\%}pa\backslash \%p=b\backslash \%p$ $\iff \backslash Leftrightarrow$ $a-b=p\ast a-b=p*$ $(l-r)\backslash left\; (l-r)\backslash right.$
$a\ast c\mathrm{\%}p=b\ast c\mathrm{\%}pa*c\backslash \%p=b*c\backslash \%p$
$\Rightarrow \backslash Rightarrow$ $(a\ast c-b\ast c)\backslash left\; (a*c-b*c)\backslash right.$ $\mathrm{\%}p=0\backslash \%p=0$
$\Rightarrow \backslash Rightarrow$ $(a-b)\backslash left\; (a-b)\backslash right.$ $\ast c\mathrm{\%}p=0*c\backslash \%p=0$
因为c和p是互质的，$\Rightarrow \backslash Rightarrow$ $(a-b)\backslash left\; (a-b)\backslash right.$ $\mathrm{\%}p=0\backslash \%p=0$
$\Rightarrow \backslash Rightarrow$ $a\mathrm{\%}p=b\mathrm{\%}pa\backslash \%p=b\backslash \%p$
2.定义集合$c_1,c_2,c_3,c_4\mathrm{.}\mathrm{.}\mathrm{.}{c}_{p-1}c\_\{1\},c\_\{2\},c\_\{3\},c\_\{4\}...c\_\{p-1\}$是p的一个完全剩余系，a与p互质，那么$a\ast c_1,a\ast c_2,a\ast c_3\mathrm{.}\mathrm{.}\mathrm{.}a\ast c_{p-1}a*c\_\{1\},a*c\_\{2\},a*c\_\{3\}...a*c\_\{p-1\}$也是p的一个完全剩余系。
假设$a\ast c_n\mathrm{\%}p=a\ast c_m\mathrm{\%}pa*c\_\{n\}\backslash \%p=a*c\_\{m\}\backslash \%p$，那么$c_n\mathrm{\%}p=c_m\mathrm{\%}pc\_\{n\}\backslash \%p=c\_\{m\}\backslash \%p$。所以命题成立。
$1\ast 2\ast 3\ast 4\ast \mathrm{.}\mathrm{.}\mathrm{.}\ast 1*2*3*4*...*$ $(p-1)\backslash left\; (p-1)\backslash right.$ $\mathrm{\%}p=a^{p-1}\ast 1\ast 2\ast 3\ast 4\ast \mathrm{.}\mathrm{.}\mathrm{.}\ast \backslash \%p=a^\{p-1\}*1*2*3*4*...*$ $(p-1)\backslash left\; (p-1)\backslash right.$ $\mathrm{\%}p\backslash \%p$
显然$1\ast 2\ast 3\ast 4\ast \mathrm{.}\mathrm{.}\mathrm{.}\ast 1*2*3*4*...*$ $(p-1)\backslash left\; (p-1)\backslash right.$与$pp$互质，所以$a^{p-1}\mathrm{\%}p=1\mathrm{\%}pa^\{p-1\}\backslash \%p=1\backslash \%p$
证毕

3.排列组合

$C(n,m)=n!\mathrm{/}(n-m)!\ast m!C(n,m)=n!/(n-m)!*m!$ 用一个数组存储$10^{6}10^6$以内的阶乘，再利用公式进行运算结果。注意的是我们计算的时候出现了取余mod，这会导致不能直接进行除法运算，我们需要将分子与分母的逆元相乘即可。
费马定理：$a\ast a^{p-2}\mathrm{\%}p=1a*a^\{p-2\}\backslash \%p=1$
根据上面证明，可以得出$a^{p-2}\mathrm{\%}pa^\{p-2\}\backslash \%p$是$aa$的逆元

const int N = 1e6 + 20;
long long int da[N], db[N];
long long C(long long n, long long m)
{
    if (n <= m)
        return 1;
    return da[n] * db[n - m] % mod * db[m] % mod;
}

main函数内代码

    da[0] = 1, db[0] = 1;
    for (int i = 1; i <= N; i++)
    {
        da[i] = da[i - 1] * i % mod;
        db[i] = db[i - 1] * qpow(i, mod - 2) % mod;
    }

容斥原理及二项式反演

容斥原理公式:
$A_1\cup A_2\cup A_3\cup \mathrm{.}\mathrm{.}\mathrm{.}{A}_n={\sum }_{1\le i\le n}{A}_i-{\sum }_{1\le i\le j\le n}{A}_i\cap A_j+{\sum }_{1\le i\le j\le k\le n}{A}_i\cap Aj\cap A_k-\mathrm{.}\mathrm{.}\mathrm{.}+(-1{)}^{n-1}\ast A_1\cap A_2\cap A_3\cap \mathrm{.}\mathrm{.}\mathrm{.}{A}_{n}A\_1\backslash cup\; A\_2\backslash cup\; A\_3\backslash cup...\; A\_n=\backslash sum\_\{1\backslash leq\; i\backslash leq\; n\}A\_i-\backslash sum\_\{1\backslash leq\; i\backslash leq\; j\backslash leq\; n\}A\_i\backslash cap\; A\_j+\backslash sum\_\{1\backslash leq\; i\backslash leq\; j\backslash leq\; k\backslash leq\; n\}A\_i\backslash cap\; Aj\backslash cap\; A\_k-...+(-1)^\{n-1\}*A\_1\backslash cap\; A\_2\backslash cap\; A\_3\backslash cap...A\_n$
$\Rightarrow \backslash Rightarrow$ ${\sum }_{k=1}^n(-1{)}^{k-1}{\sum }_{1\le i\le j\le \mathrm{.}\mathrm{.}\mathrm{.}\le k\le n}{A}_i\cap A_j\cap \mathrm{.}\mathrm{.}\mathrm{.}\cap A_k\backslash sum\_\{k=1\}\; ^\{n\}\; (-1)^\{k-1\}\backslash sum\_\{1\backslash leq\; i\backslash leq\; j\backslash leq...\backslash leq\; k\backslash leq\; n\}A\_i\backslash cap\; A\_j\backslash cap\; ...\backslash cap\; A\_k$
证明:定义一个元素被m个元素所共有
${\sum }_{k=1}^m(-1{)}^{k-1}C(m,k)=C(m,1)-C(m,2)+C(m,3)-\mathrm{.}\mathrm{.}\mathrm{.}+(-1{)}^{m-1}\ast C(m,m)\backslash sum\_\{k=1\}\; ^m\; (-1)^\{k-1\}C(m,k)=C(m,1)-C(m,2)+C(m,3)-...+(-1)^\{m-1\}*C(m,m)$
$\Rightarrow \backslash Rightarrow$ $C(m,0)-C(m,0)+C(m,1)-C(m,2)+C(m,3)-\mathrm{.}\mathrm{.}\mathrm{.}+(-1{)}^{k-1}C(m,m)C(m,0)-C(m,0)+C(m,1)-C(m,2)+C(m,3)-...+(-1)^\{k-1\}C(m,m)$
$\Rightarrow \backslash Rightarrow$ $1-{\sum }_{k=0}^n(-1{)}^k\ast C(m,k)1-\backslash sum\_\{k=0\}\; ^n\; (-1)^\{k\}*C(m,k)$
$\Rightarrow \backslash Rightarrow$ $1-(1-1{)}^m=11-(1-1)^m=1$
这说明右式的每个元素都仅仅算了一次
二项式反演：
定义$f(n)f(n)$为任意n个集合的交集的元素个数，$g(n)g(n)$为任意n个集合的补集的交集的元素个数。
特别的定义$f(0)=U,g(0)=U\mathrm{，}Uf(0)=U,g(0)=U，U$代表全集
$\overline{A_1\cup A_2\cup \mathrm{.}\mathrm{.}\mathrm{.}\cup A_k}=\overline{A_1}\cap \overline{A_2}\cap \mathrm{.}\mathrm{.}\mathrm{.}\cap \overline{A_k}\backslash overline\{A\_1\backslash cup\; A\_2\backslash cup...\backslash cup\; A\_k\}=\backslash overline\{A\_\{1\}\}\backslash cap\; \backslash overline\{A\_\{2\}\}\backslash cap...\backslash cap\backslash overline\{A\_\{k\}\}$
$\Rightarrow \backslash Rightarrow$ $U-\overline{A_1}\cap \overline{A_2}\cap \mathrm{.}\mathrm{.}\mathrm{.}\cap \overline{A_k}=A_1\cup A_2\cup \mathrm{.}\mathrm{.}\mathrm{.}\cup A_{k}U-\backslash overline\{A\_\{1\}\}\backslash cap\; \backslash overline\{A\_\{2\}\}\backslash cap...\backslash cap\backslash overline\{A\_\{k\}\}=A\_1\backslash cup\; A\_2\backslash cup...\backslash cup\; A\_k$
$\Rightarrow \backslash Rightarrow$ $\overline{A_1}\cap \overline{A_2}\cap \mathrm{.}\mathrm{.}\mathrm{.}\cap \overline{A_k}=U-A_1\cup A_2\cup \mathrm{.}\mathrm{.}\mathrm{.}\cup A_k\backslash overline\{A\_\{1\}\}\backslash cap\; \backslash overline\{A\_\{2\}\}\backslash cap...\backslash cap\backslash overline\{A\_\{k\}\}=U-A\_1\backslash cup\; A\_2\backslash cup...\backslash cup\; A\_k$
即$g(n)=U-{\sum }_{k=1}^n(-1{)}^{k-1}{\sum }_{1\le i\le j\le \mathrm{.}\mathrm{.}\mathrm{.}\le k\le n}{A}_i\cap A_j\cap \mathrm{.}\mathrm{.}\mathrm{.}\cap A_{k}g(n)=U-\backslash sum\_\{k=1\}\; ^\{n\}\; (-1)^\{k-1\}\backslash sum\_\{1\backslash leq\; i\backslash leq\; j\backslash leq...\backslash leq\; k\backslash leq\; n\}A\_i\backslash cap\; A\_j\backslash cap\; ...\backslash cap\; A\_k$
容斥原理公式转变(细看容斥原理证明)
$\Rightarrow \backslash Rightarrow$ $g(n)=U-{\sum }_{k=1}^n(-1{)}^{k-1}\ast C(n,k)\ast f(k)g(n)=U-\backslash sum\_\{k=1\}\; ^n\; (-1)^\{k-1\}*C(n,k)*f(k)$
又因为$f(0)=U,f(0)=U,$ $\Rightarrow \backslash Rightarrow$ $g(n)={\sum }_{k=0}^n(-1{)}^k\ast C(n,k)\ast f(k)g(n)=\backslash sum\_\{k=0\}\; ^n\; (-1)^\{k\}*C(n,k)*f(k)$
如果我们把补集与原集合进行颠倒，公式仍然成立。
即:$f(n)={\sum }_{k=0}^n(-1{)}^k\ast C(n,k)\ast g(k)f(n)=\backslash sum\_\{k=0\}\; ^n\; (-1)^\{k\}*C(n,k)*g(k)$
通用公式:$f(n)={\sum }_{k=i}^{n}C(n,k)\ast g(k)f(n)=\backslash sum\_\{k=i\}\; ^nC(n,k)*g(k)$ $\Rightarrow \backslash Rightarrow$ $g(n)={\sum }_{k=i}^n(-1{)}^{n-k}\ast c(n,k)\ast f(k)g(n)=\backslash sum\_\{k=i\}\; ^n(-1)^\{n-k\}*c(n,k)*f(k)$

题解

用不超过k种颜色涂满n个盒子，要求相邻的盒子颜色不同，方案数为:$x_k=k\ast (k-1{)}^{n-1}x\_k=k*(k-1)^\{n-1\}$
从k种颜色种选择i种颜色涂满n个盒子，要求相邻的盒子颜色不同，方案数最多为:$y_k=C(k,i)\ast i\ast (i-1{)}^{n-1}y\_k=C(k,i)*i*(i-1)^\{n-1\}$，这里面一定有重复的。比如我们提前挑选出1，2这两种颜色，然后再从剩下的颜色中随机选一种颜色，有k-2种可能，但是这些可能的情况中，只用1,2颜色涂色的情况都被算过。
根据题意可以写出:
定义$t_{k}t\_k$表示恰好用k种颜色涂满n个盒子，相邻盒子颜色不同的方案数
$x_n={\sum }_{k=1}^{n}C(n,k)\ast t_k=C(n,1)\ast t_1+C(n,2)\ast t_2+\mathrm{.}\mathrm{.}\mathrm{.}C(n,n)\ast t_{n}x\_n=\backslash sum\_\{k=1\}\; ^nC(n,k)*t\_k=\; C(n,1)*t\_1+C(n,2)*t\_2+...C(n,n)*t\_n$
根据二项式反演，得:$t_n={\sum }_{k=1}^n(-1{)}^{n-k}\ast x_{k}t\_n=\backslash sum\_\{k=1\}\; ^n\; (-1)^\{n-k\}*x\_k$
然后共有m种颜色，挑出k种颜色涂满n个盒子的方案数即为：
$ans=C(m,k)\ast t_{n}ans=C(m,k)*t\_n$
注：m的数据范围高达$10^{9}10^9$，所以使用公式:$m\ast (m-1)\ast (m-2)\ast \mathrm{.}\mathrm{.}\mathrm{.}\ast (m-n+1)\mathrm{/}n!m*(m-1)*(m-2)*...*(m-n+1)/n!$
AC代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using pll = pair<ll, ll>;
const ll mod = 1e9 + 7;
long long qpow(long long n, long long m)
{
    if (n == 0 || n == 1)
        return n;
    long long ans = 1;
    while (m)
    {
        if (m & 1)
            ans = ans * n % mod;
        n = n * n % mod;
        m >>= 1;
    }
    return ans % mod;
}
const int N = 1e6 + 20;
long long int da[N], db[N];
//da表示阶乘,db表示逆元
long long C(long long n, long long m)
{
    if (n <= m)
        return 1;
    return da[n] * db[n - m] % mod * db[m] % mod;
}
void dilingtian()
{
    long long n, m, k;
    cin >> n >> m >> k;
  //特例，只有一个盒子的时候
    if (n == 1)
    {
        if (k == 1)
            cout << m << endl;
        else
            cout << 0 << endl;
        return;
    }
    long long x = 1;
    long long ans = 0;
    for (long long i = k; i >= 1; i--)
      //根据公式发现，第k个元素一定为正，所以反向计算
    {
        ans = (ans + x * C(k, i) * i % mod * qpow(i - 1, n - 1) % mod + mod) % mod;
        x *= -1;
    }
    for (ll i = m - k + 1; i <= m; i++)
        ans = ans * i % mod;
    ans = ans * db[k] % mod;
    cout << (ans + mod) % mod << endl;
}
int main(void)
{
    da[0] = 1, db[0] = 1;
    for (int i = 1; i <= N; i++)
    {
        da[i] = da[i - 1] * i % mod;
        db[i] = db[i - 1] * qpow(i, mod - 2) % mod;
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        dilingtian();
    return 0;
}