跳转至

ABC172E

知识点

  • 容斥原理
  • 组合数学

题意简述

求长度为 \(n\),满足以下条件的序列对 \((A, B)\) 的个数:

  • \(\forall i \in [1, n], A_i \in [1, m], B_i \in [1, m]\)
  • \(\forall i \in [1, n], A_i \neq B_i\)
  • \(\forall 1 \le i < j \le n, A_i \neq A_j, B_i \neq B_j\)

答案对 \(10^9 + 7\) 取模1

数据范围:\(1 \le n \le m \le 5\cdot10^5\)

解题思路

首先我们可以发现,满足 \(\forall i \in S, A_i = B_i\) 的序列对 \((A, B)\)\(A_{m}^{\left|S\right|}\cdot\left(A_{m - \left|S\right|}^{n - \left|S\right|}\right)^2\) 个。

然后根据容斥原理,我们发现答案为 \(\sum_{S \subseteq [1, n]}(-1)^{\left|S\right|}\cdot A_{m}^{\left|S\right|}\cdot\left(A_{m - \left|S\right|}^{n - \left|S\right|}\right)^2\)

(加上 \(\left|S\right| = 0\) ,减去 \(\left|S\right| = 1\),加上 \(\left|S\right| = 2\)……)

枚举子集是不必要的,我们可以从组合意义的角度来处理上式,

将所有 \(\left|S\right| = k\) 的所有子集 \(S\) 合并处理,这样的 \(S\)\(\dbinom{n}{k}\) 个。

答案即为 \(\sum_{k = 0}^{n}\dbinom{n}{k}(-1)^k\cdot A_{m}^{k}\cdot\left(A_{m - k}^{n - k}\right)^2\)

代码实现

核心部分已用高亮标出。

Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define LL long long

const int mod = 1e9 + 7;
const int N = 5e5 + 5;

int n, m, fac[N] = { 1 }, inv[N] = { 1 };
LL ans;

int mul(int ta, int tb) {
    int ret;
    __asm__ __volatile__ ("\tmull %%ebx\n\tdivl %%ecx\n":"=d"(ret):"a"(ta), "b"(tb), "c"(mod));
    return ret;
}

int qpow(int bas, int po) {
    int res = 1;
    while(po) {
        if(po & 1)
            res = mul(res, bas);
        bas = mul(bas, bas);
        po >>= 1;
    }
    return res;
}

int C(int tn, int tm) {
    return mul(fac[tn], mul(inv[tm], inv[tn - tm]));
}

int A(int tn, int tm) {
    return mul(fac[tn], inv[tn - tm]);
}

int32_t main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++i)
        fac[i] = mul(fac[i - 1], i);
    inv[m] = qpow(fac[m], mod - 2);
    for(int i = m; i >= 2; --i)
        inv[i - 1] = mul(inv[i], i);
    for(int i = 0; i <= n; ++i) {
        int flg = (i & 1) ? -1 : 1;
        int tmp = mul(C(n, i), mul(A(m, i), qpow(A(m - i, n - i), 2)));
        ans += flg * tmp;
        ans %= mod, (ans += mod) %= mod;
    }
    printf("%lld", ans);
    return 0;
}

  1. 原题链接: E - NEQ