Submission #9582191

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int MOD = 998244353;

int madd(int a, int b) {
	int res = a + (b < 0 ? b + MOD : b);
	return (res >= MOD ? res - MOD : res);
}

const int N = 10;
const int M = 1 << N;
int col[N][N];
int dp[M][M];
int alts[M * M][2*N+1];

bool check(int m0, int m1) {
	vector<int> rc(N, 0), cc(N, 0);
	for (int y = 0; y < N; ++y) {
		if (! (m0 & (1 << y))) rc[y] = 3;
	}
	for (int x = 0; x < N; ++x) {
		if (! (m1 & (1 << x))) cc[x] = 3;
	}
	for (int y = 0; y < N; ++y) {
		if (! (m0 & (1 << y))) continue;
		for (int x = 0; x < N; ++x) {
			if (! (m1 & (1 << x))) continue;
			rc[y] |= col[y][x];
			cc[x] |= col[y][x];
		}
	}
	bool works = true;
	for (auto v : rc) works &= (v == 3);
	for (auto v : cc) works &= (v == 3);
	return works;
}

// Calculate alternating sum over submasks
int altSum(int m0, int m1) {
	int m = m0 | (m1 << N);
	alts[m][2*N] = dp[m0][m1];
	for (int j = 2*N - 1; j >= 0; --j) {
		if (m & (1 << j)) {
			alts[m][j] = madd(alts[m][j+1], -alts[m ^ (1 << j)][j+1]);
		} else {
			alts[m][j] = alts[m][j+1];
		}
	}
	return alts[m][0];
}

// Set value of DP at mask m0 m1 val.
void setDP(int m0, int m1, int val) {
	dp[m0][m1] = val;
	altSum(m0, m1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int h, w;
	cin >> h >> w;
	for (int y = 0; y < h; ++y) {
		string row;
		cin >> row;
		for (int x = 0; x < w; ++x) col[y][x] = 1 + (row[x] == '#');
	}

	// If any operations are applied, then some rows or some columns must be completely black or white
	// Delete those columns and rows and solve recursively. We need to do inclusion-exclusion to not double-count solutions.
	// Where does the initial state of the grid matter? If in some subgrid we have no completely black or white columns or rows,
	// we can add one to the solution for that subgrid!
	// To calculate the answer sufficiently fast, we'll need to do some prefix sums.

	int h0 = 1 << h;
	int h1 = 1 << w;
	for (int m0 = 0; m0 < h0; ++m0) {
		setDP(m0, 0, 1);
	}
	for (int m1 = 0; m1 < h1; ++m1) {
		setDP(0, m1, 1);
	}

	for (int m0 = 0; m0 < h0; ++m0) {
		int rc = __builtin_popcount(m0);
		if (rc == 0) continue;
		for (int m1 = 0; m1 < h1; ++m1) {
			int cc = __builtin_popcount(m1);
			if (cc == 0) continue;

			int res = check(m0, m1);
			// Inclusion-exclusion, paint only multiple rows
			for (int s0 = m0;; s0 = (s0 - 1) & m0) {
				int pw = rc - __builtin_popcount(s0);
				if (pw > 1) {
					ll mult = (ll)(pw & 1 ? 1 : MOD - 1) * ((1 << pw) - 2) % MOD;
					res = (res + (ll)mult * dp[s0][m1]) % MOD;
				}
				if (s0 == 0) break;
			}
			// Inclusion-exclusion, paint only multiple columns
			for (int s1 = m1;; s1 = (s1 - 1) & m1) {
				int pw = cc - __builtin_popcount(s1);
				if (pw > 1) {
					ll mult = (ll)(pw & 1 ? 1 : MOD - 1) * ((1 << pw) - 2) % MOD;
					res = (res + (ll)mult * dp[m0][s1]) % MOD;
				}
				if (s1 == 0) break;
			}


			// Inclusion-exclusion, paint both rows and columns
			int add = MOD - altSum(m0, m1);
			add = madd(add, add);
			res = madd(res, add);

			setDP(m0, m1, res);
		}
	}
	cout << dp[h0-1][h1-1] << '\n';
}

Submission Info

Judge Result