模拟赛题讲解[9]

来自 Roundgod 2022-07-29 noi.ac #2693

原题来自 ABC172E NEQ

问题描述：

给定 $n,m$，你需要计算满足以下条件的数组对 $A=[a_1,a_2,\dots,a_n]$ 和 $B=[b_1,b_2,\dots,b_n]$ 的个数:

对于所有 $1\leq i\leq n$ ，都有 $1\leq a_i\leq m$ 以及 $1\leq b_i\leq m$.
对于所有 $1\leq i\leq n$ ，都有 $a_i\neq b_i$.
对于所有的 $1\leq i\lt j\leq n$ ，都有 $a_i\neq a_j$ 且 $b_i\neq b_j$.

由于答案可能过大，你需要输出答案对 $10^9+7$取模后的值。

输入格式：

输入第一行包含一个整数 $t(1\leq t\leq 10)$ ，表示数据的组数。对于每组测试数据，输入为一行，包含两个整数 $n,m$。

输出格式：

对于每组测试数据，在一行中输出一个整数，表示答案。

输入1：

2 2
2 3
1 1
10 10
114514 1919810

输出1

样例说明：

对于样例的第一组测试数据, 合法数组对有以下 $2$ 种:

$A=[1,2],B=[2,1];A=[2,1],B=[1,2]$

数据范围：

对于 $20\%$ 的数据，$1\leq n\leq m\leq 10$

对于 $100\%$ 的数据，$1\leq n\leq m\leq 2\times 10^6$

题解：

显然的容斥题。设性质 $p_i:a_i=b_i,S \subseteq [m]$ （这里 $[m]=\{1,2,\dots,m\}$）

则我们可以用这个经典公式来计算题目要求的 $a_i \ne b_i$ （注意公式中是 $|S|$ 而不是 $|S|+1$ ）

$\sum_{S \subseteq [m]} (-1)^{|S|} \left|N(S)\right|$

考虑这里的 $N(S)$ 如何计算。不难发现

$N(S) = \dbinom{m}{i}i! \left[ \left((n-i)! \right)\dbinom{m-i}{n-i} \right]^2$

中括号前面的指对 $S$ 指定的这 $i$ 个 $a_j=b_j$ 染色，后者就是对 $a_j \ne b_j$ 的染色

因为 $a,b$ 此时染色相互独立，所以直接乘法原理（就是那个平方）

~~你敢信我模拟赛这么水的题没想出来，主要还是组合数学的不扎实~~

所以答案就是

$\sum_{i=0}^{n}(-1)^i\dbinom{n}{i}\dbinom{m}{i}i! \left[ \left((n-i)! \right)\dbinom{m-i}{n-i} \right]^2$

这里的 $i$ 就是在枚举 $|S|$ ， $\binom{n}{i}$ 就是大小等于 $i$ 的 $S$ 的个数

然后预处理一下阶乘啊逆元啊什么的就好啦

时间复杂度 $\mathcal{O}(Qn)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e6+15)

const int p=1e9+7;
int n,m,fac[N],invf[N];
int qpow(int a,int b)
{
    int ans=1,base=a%p;
    while(b)
    {
        if(b&1) ans=ans*base%p;
        base=base*base%p;
        b>>=1;
    }
    return ans;
}
int inv(int x){return qpow(x,p-2);}
void init()
{
    invf[0]=fac[0]=1;
    for(int i=1; i<=N-5; i++)
        fac[i]=fac[i-1]*i%p;
    invf[N-5]=inv(fac[N-5]);
    for(int i=N-5-1; i>=1; i--)
        invf[i]=invf[i+1]*(i+1)%p;
}
int A(int n,int k)
{
    if(n<k) return 0;
    return fac[n]*invf[n-k]%p;
}
int C(int n,int k)
{
    if(n<k) return 0;
    return fac[n]*invf[k]%p*invf[n-k]%p;
}
void add(int &x,int y){x+=y;if(x>=p)x-=p;}
void dec(int &x,int y){x-=y;if(x<0)x+=p;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    init(); int Q; cin >> Q;
    while(Q--)
    {
        cin >> n >> m;
        int res=0;
        for(int i=0; i<=n; i++)
        {
            int tmp=C(n,i)%p*A(m,i)%p*A(m-i,n-i)%p*A(m-i,n-i)%p;
            if(i&1) dec(res,tmp); else add(res,tmp);
        }
        cout << res << '\n';
    }
    return 0;
}