「Solution」HDU-6314 Matrix

确实可以推广到一般性题目

Matrix

link

分析

原来一直不理解容斥，这道题可以作为一个一般性容斥题目的母题。

---

首先可以考虑只有行的时候。

设$g_i$为至少有$i$行是黑色的方案数。

显然$g_i = \sum_\limits{i=a}^{n} f_i \dbinom{n}{i} \times 2 ^ {n - i}$其中$f_k$为容斥系数。

那么可以知道$\sum_\limits{i=a}^n f_i\dbinom{n}{i} = 1$

就可以开始推式子了。
$$ \begin{aligned} 1 &= \sum_\limits{i=a}^n f_i\dbinom{n}{i} \\ 1 &= \sum_\limits{i=a}^{n-1} f_i\dbinom{n}{i} + f_n\\ 1 &= \sum_\limits{i=a}^{n-1} f_i\Big(\dbinom{n - 1}{i - 1} + \dbinom{n - 1}{i}\Big) + f_n \\ f_n &= 1 - \sum_\limits{i=a}^{n-1} f_i\Big(\dbinom{n - 1}{i - 1} + \dbinom{n - 1}{i}\Big)\\ f_n &= 1 - \sum_\limits{i=a}^{n-1}\dbinom{n - 1}{i - 1} f_i - \sum_\limits{i=a}^{n-1} \dbinom{n - 1}{i} f_i \\ f_n &= -\sum_\limits{i=a}^{n-1} \dbinom{n - 1}{i - 1} f_i \end{aligned} $$

然后加入列的贡献。

$g_i = \sum_\limits{i=a}^{n} \sum_\limits{j=b}^{m} f_{1,i} \dbinom{n}{i} f_{2,j}\dbinom{m}{j} \times 2 ^ {(n - i) \times (m - j)}$

时间复杂度是$\mathcal{O(n^2 + m^2 + nm)}$

显然不会超时。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXN = 3e3 + 5;
const int Mod = 998244353;

int n, m, a, b;
int f[5][MAXN];

LL C[MAXN][MAXN], ans;

LL qpow(LL x, int y) {
    LL res = 1;
    while (y) {
        if (y & 1) res = res * x % Mod;
        x = x * x % Mod;
        y >>= 1;
    }
    return res;
}

int main() {

    C[0][0] = 1ll;
    for (int i = 1; i <= 3000; i++) {
        C[i][0] = 1ll;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod;
        }
    }

    while (scanf("%d %d %d %d", &n, &m, &a, &b) != EOF) {

        ans = 0;
        memset(f, 0, sizeof(f));

        f[1][a] = 1;
        for (int i = a + 1; i <= n; i++) {
            for (int j = a; j < i; j++) {
                f[1][i] = (f[1][i] - C[i - 1][j - 1] * f[1][j] % Mod + Mod) % Mod;
            }
        }

        f[2][b] = 1;
        for (int i = b + 1; i <= m; i++) {
            for (int j = b; j < i; j++) {
                f[2][i] = (f[2][i] - C[i - 1][j - 1] * f[2][j] % Mod + Mod) % Mod;
            }
        }

        for (int i = a; i <= n; i++) {
            for (int j = b; j <= m; j++) {
                ans = (ans + f[1][i] * C[n][i] % Mod * f[2][j] % Mod * C[m][j] % Mod * qpow(2, (n - i) * (m - j)) % Mod);
            }
        }

        printf("%lld\n", ans % Mod);

    }

    return 0;
}