多校2 hdu 6314 Matrix （广义容斥原理）

127 阅读 0 评论 84 点赞

我是靠谱客的博主开心犀牛，这篇文章主要介绍多校2 hdu 6314 Matrix （广义容斥原理），现在分享给大家，希望可以做个参考。

题目链接：哆啦A梦传送门

题意：给n,m,a,b，让你再n*m方格中，至少要有a行，b列黑，有多少种不同的方案。

题解：广义容斥原理：参考链接：广义容斥原理

参考链接：https://blog.csdn.net/Binary_Heap/article/details/81839405

可以先考虑行，再考虑二维。

我们用g(k)表示至少有k行全黑的方案数，容斥： $large {color{red} g(k)=sum_{i=k}^{n}f(i)*binom{n}{i}*2^{n-i}}$

因为是至少，所以需要容斥， $large {color{blue} binom{n}{i}}$ 表示n行选i行， $large {color{blue} 2^{n-i}}$ 表示其中剩余的行随意，f(i)为容斥系数，我们需要递推出这个容斥系数.

每个行数为j的答案计算贡献只能算一次，所以： $large sum_{i=k}^{j}f(i)*binom{j}{i}}=1$ ，我们解释下为什么每个行数为j的答案计算贡献时只算了一次？

推导：我们先举个一般例子，例如，有三块奖牌，得A奖牌的人数为x，得B奖牌的人数为y，得C奖牌的人数为z，问：有多少人获奖？

对于这个例子，我们就用一般容斥原理去做， $large {color{blue} sum_{i=1}^{3}f(i)*binom{3}{i}*sum}={color{blue} sum_{i=1}^{3}(-1)^{i+1}*binom{3}{i}*sum}$ ,sum表示每种方案的总数。并且我们知道

$large {color{blue} sum_{i=1}^{3}f(i)*binom{3}{i}=}{color{red} 1}$ （至少1条件）( i从1开始）。

那么对于这道题 $large sum_{i=k}^{j}f(i)*binom{j}{i}}=1$ （至少k条件）(i从k开始）。我们假设j>i，那么存在取j行为黑时，也把取i行为黑的情况也囊括在里面，故我们需要容斥。

那么现在我们来递推出本题容斥系数：

$large {color{red} sum_{i=k}^{n}f(i)*binom{n}{i}}=$ $large sum_{i=k}^{n-1}f(i)*binom{n}{i}+f(n)$

$large =sum_{i=k}^{n-1}f(i)*(binom{n-1}{i}+binom{n-1}{i-1})+f(n)$

$large =sum_{i=k}^{n-1}(f(i)*binom{n-1}{i}+f(i)binom{n-1}{i-1})+f(n)$

$large =1+sum_{i=k}^{n-1}f(i)binom{n-1}{i-1}+f(n)$

因为 $large sum_{i=k}^{n}f(i)*binom{n}{i}=1$ ，故 $large {color{red} f(n)=-sum_{i=k}^{n-1}f(i)binom{n-1}{i-1}}$ 。

剩下的就用O(n^2)+O(m^2)递推求容斥系数了，注意 fa(a)=fb(b)=1。由前面的式子很容易得出。

那么最终答案就为 $large {color{red} sum_{i=a}^{n}sum_{j=b}^{m} fa(i)*binom{n}{i}*fb(j) *binom{m}{j}*2^{(n-i)(m-j)} }$ 。

复制代码

#include <cstdio>
const int maxn = 3000;
const int mod = 998244353;
typedef long long LL;
int n, m, a, b;
int fa[maxn + 10], fb[maxn + 10];
int pow2[maxn * maxn + 10], c[maxn + 10][maxn + 10];
void init() {
///预处理2的n次方
pow2[0] = 1;
for(int i = 1; i <= maxn * maxn; i ++)
pow2[i] = (pow2[i - 1] * 2LL) % mod;
///杨辉三角求组合数
for(int i = 0; i <= maxn; i ++) {
c[i][0] = c[i][i] = 1;
for(int j = 1; j < i; j ++)
c[i][j] = (1LL * c[i-1][j-1] + c[i-1][j]) % mod;
}
}
void calc_f() {
///预处理行的容斥系数
fa[a] = 1;
for(int i = a + 1; i <= n; i ++) {
fa[i] = 0;
for(int j = a; j < i; j ++)
fa[i] = (fa[i] + 1LL * c[i-1][j-1] * fa[j] % mod) % mod;
fa[i] = ((-fa[i]) % mod + mod) % mod;
}
///预处理列的容斥系数
fb[b] = 1;
for(int i = b + 1; i <= m; i ++) {
fb[i] = 0;
for(int j = b; j < i; j ++)
fb[i] = (fb[i] + 1LL * c[i-1][j-1] * fb[j] % mod) % mod;
fb[i] = ((-fb[i]) % mod + mod) % mod;
}
}
int main() {
init();
while(~ scanf("%d%d%d%d", &n, &m, &a, &b)) {
calc_f();
int ans = 0;
for(int i = a; i <= n; i ++)
for(int j = b; j <= m; j ++)
ans = (ans + 1LL * fa[i] * c[n][i] % mod * fb[j] % mod * c[m][j] % mod * pow2[(n - i) * (m - j)] % mod) % mod;
printf("%dn", (ans % mod + mod) % mod);
}
return 0;
}

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 <cstdio>
const int maxn = 3000;
const int mod = 998244353;
typedef long long LL;
int n, m, a, b;
int fa[maxn + 10], fb[maxn + 10];
int pow2[maxn * maxn + 10], c[maxn + 10][maxn + 10];
void init() {
///预处理2的n次方
pow2[0] = 1;
for(int i = 1; i <= maxn * maxn; i ++)
pow2[i] = (pow2[i - 1] * 2LL) % mod;
///杨辉三角求组合数
for(int i = 0; i <= maxn; i ++) {
c[i][0] = c[i][i] = 1;
for(int j = 1; j < i; j ++)
c[i][j] = (1LL * c[i-1][j-1] + c[i-1][j]) % mod;
}
}
void calc_f() {
///预处理行的容斥系数
fa[a] = 1;
for(int i = a + 1; i <= n; i ++) {
fa[i] = 0;
for(int j = a; j < i; j ++)
fa[i] = (fa[i] + 1LL * c[i-1][j-1] * fa[j] % mod) % mod;
fa[i] = ((-fa[i]) % mod + mod) % mod;
}
///预处理列的容斥系数
fb[b] = 1;
for(int i = b + 1; i <= m; i ++) {
fb[i] = 0;
for(int j = b; j < i; j ++)
fb[i] = (fb[i] + 1LL * c[i-1][j-1] * fb[j] % mod) % mod;
fb[i] = ((-fb[i]) % mod + mod) % mod;
}
}
int main() {
init();
while(~ scanf("%d%d%d%d", &n, &m, &a, &b)) {
calc_f();
int ans = 0;
for(int i = a; i <= n; i ++)
for(int j = b; j <= m; j ++)
ans = (ans + 1LL * fa[i] * c[n][i] % mod * fb[j] % mod * c[m][j] % mod * pow2[(n - i) * (m - j)] % mod) % mod;
printf("%dn", (ans % mod + mod) % mod);
}
return 0;
}