HDU6314 Matrix 题解

link

广义容斥。

先从一维考虑。令 \(ans(a)\) 为至少有 \(a\) 列（行）全为黑的方案数。

考虑这样的模型很像容斥。但是我们并不知道容斥系数，不妨把它们设出来 （\(f_i\)）：

\(ans(a)=\sum_{i=a}^nf_{i}\binom {n} {i}2^{n-i}\)。

根据容斥的目的，现在我们的目标是确定容斥系数，使每种结果 出现且仅出现一次。

则考虑一种方案（令其全为黑的行数为 \(t\) ）的贡献 \(\sum_{i=a}^tf_i\binom {t} {i}\)（读者需仔细读懂本式）。

则 \(\sum_{i=a}^tf_i\binom {t} {i}=1\)。

由于我们想找 \(f\) 的具体数值，不妨找到 \(f\) 之间的关系

\(=> f_t+\sum_{i=a}^{t-1}\binom {t} {i}f_i=1\)，此时我们想尽量将原式化为刚才的形式，则：

\(=> f_t+\sum_{i=a}^{t-1}(\binom{t-1} {i}f_i+\binom {t-1} {i-1}f_i)=1\)

\(=>f_t+1+\sum_{i=a}^{t-1}\binom {t-1} {i-1}f_i=1\)。

\(=>f_t=-\sum_{i=a}^{t-1}\binom {t-1} {i-1}f_i\)，随便将 \(f\) 赋值，计算 \(f\) 的复杂度是 \(\mathcal {O}(n^2)\) 的，可以接受。

初始值: \(f_a=1\)。（由 \(\sum_{i=a}^af_i\binom {a} {i}=1\) 知）

现在将其拓展至二维。

\(ans(a,b)=\sum_{i=a}^n\sum_{j=b}^mf_if'_j\binom n a\binom m b2^{(n-i)(m-j)}\)（不要问我 \(f,f'\) 为什么乘起来，我只能说是套路）

则 \(\sum_{i=a}^s\sum_{j=b}^tf_if'_j\binom s i\binom t j=1\)。

则 \(\sum_{i=a}^sf_i\binom s i\sum_{j=b}^tf'_j\binom t j=1\)。

这里可以理解成先保证行中至少有 \(b\) 个为黑，再将它们缩成一维。所以二维的系数分别等于他们一维时的系数。所以得证。然后预处理出 \(f,f'\) 后直接做就可以了。时间复杂度：\(\mathcal O(n^2+m^2+nm)\)。

但是这题卡常。

#include 
#include 
#include 
#include 
#define LL long long
using namespace std;
const int Mod = 998244353, MAXN = 3005;
int n, m, s, t;
int fa[MAXN], fb[MAXN], power[MAXN * MAXN], C[MAXN][MAXN];
int main() {
	for(int i = 0; i <= 3000; i ++) C[i][0] = 1;
	for(int i = 0; i <= 3000; i ++) for(int j = 1; j <= i; j ++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod;
	power[0] = 1;
	for(int i = 1; i <= 3000 * 3000; i ++) power[i] = power[i - 1] * 2 % Mod;
	while(~scanf("%d%d%d%d", &n, &m, &s, &t)) {
		int ans = 0; fa[s] = fb[t] = 1;
		for(int i = s + 1; i <= n; i ++) {
            int sum_ = 0; 
            for(int j = s; j <= i - 1; j ++) {
                sum_ += 1LL * fa[j] * C[i - 1][j - 1] % Mod;
                if(sum_ >= Mod) sum_ -= Mod; 
            }
            if(sum_ > 0) sum_ -= Mod;
            fa[i] = -sum_;
        }
        for(int i = t + 1; i <= m; i ++) {
            int sum_ = 0; 
            for(int j = t; j <= i - 1; j ++) {
                sum_ += 1LL * fb[j] * C[i - 1][j - 1] % Mod;
                if(sum_ >= Mod) sum_ -= Mod; 
            }
            if(sum_ > 0) sum_ -= Mod;
            fb[i] = -sum_;
        }
		for(int i = s; i <= n; i ++) {
			LL fuck = 1, qwq = power[n - i];
			for(int j = m; j >= t; j --) {
				ans += 1LL * fa[i] * fb[j] % Mod * C[n][i] % Mod * C[m][j] % Mod * fuck % Mod;
				if(ans >= Mod) ans -= Mod;
				fuck = fuck * qwq % Mod;
			}
		}
		printf("%d\n", (ans + Mod) % Mod);
	}
	return 0;
}