526互联

AtCoder Beginner Contest 228 G Digits on Grid

发布时间 2023-06-27 21:58:14作者: zltzlt

洛谷传送门

AtCoder 传送门

？这啥啊，不会。

考虑行和列分别作为左部点和右部点建二分图（实际上这个建图只是辅助理解，不需要显式建图），每个左部点和每个右部点，边权为格子中的数。

容易想到一个 dp，设 \(f_{i, j}\) 为走了 \(i\) 步，当前在点 \(j\)，走过的所有边权组成的不同整数的数量。但是你会发现根本没法做，因为不同的状态有可能包含相同的整数，很尴尬。

然后就是奇妙的部分了。更改状态为 \(f_{i, S}\) 表示走了 \(i\) 步，不同整数的数量，使得所有走过这些整数的路径的终点集合为 \(S\) 的方案数。注意到如果 \(S\) 不同，那走过的整数一定不同。因此这个状态设计是没问题的。

转移是平凡的。枚举下一步填的位，沿着边权为它的边走，即可得知终点集合。

注意到若 \(i\) 为偶数，\(S\) 为左部点集子集；若 \(i\) 为奇数，\(S\) 为右部点集子集。所以朴素实现的时间复杂度是 \(O(10N (2^H + 2^W) HW)\)。显然可以预处理一些东西做到更优，但是这个复杂度足以通过了。

code 
// Problem: G - Digits on Grid
// Contest: AtCoder - TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228)
// URL: https://atcoder.jp/contests/abc228/tasks/abc228_g
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 610;
const int maxm = (1 << 10) + 50;
const ll mod = 998244353;

ll n, m, K, a[15][15], f[maxn][maxm];

void solve() {
	scanf("%lld%lld%lld", &n, &m, &K);
	K <<= 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			scanf("%1lld", &a[i][j]);
		}
	}
	f[0][(1 << n) - 1] = 1;
	for (int i = 1; i <= K; ++i) {
		if (i & 1) {
			for (int S = 1; S < (1 << n); ++S) {
				if (!f[i - 1][S]) {
					continue;
				}
				for (int d = 1; d <= 9; ++d) {
					int T = 0;
					for (int i = 0; i < n; ++i) {
						if ((~S) & (1 << i)) {
							continue;
						}
						for (int j = 0; j < m; ++j) {
							if (a[i][j] == d) {
								T |= (1 << j);
							}
						}
					}
					f[i][T] = (f[i][T] + f[i - 1][S]) % mod;
				}
			}
		} else {
			for (int S = 0; S < (1 << m); ++S) {
				if (!f[i - 1][S]) {
					continue;
				}
				for (int d = 1; d <= 9; ++d) {
					int T = 0;
					for (int j = 0; j < m; ++j) {
						if ((~S) & (1 << j)) {
							continue;
						}
						for (int i = 0; i < n; ++i) {
							if (a[i][j] == d) {
								T |= (1 << i);
							}
						}
					}
					f[i][T] = (f[i][T] + f[i - 1][S]) % mod;
				}
			}
		}
	}
	ll ans = 0;
	for (int S = 1; S < (1 << n); ++S) {
		ans = (ans + f[K][S]) % mod;
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}