結果

問題 No.1397 Analog Graffiti
ユーザー QCFiumQCFium
提出日時 2021-02-14 22:31:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 5,824 ms / 10,000 ms
コード長 9,854 bytes
コンパイル時間 2,862 ms
コンパイル使用メモリ 203,380 KB
実行使用メモリ 16,864 KB
最終ジャッジ日時 2024-07-22 10:20:30
合計ジャッジ時間 48,680 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 3 ms
6,944 KB
testcase_02 AC 5,801 ms
16,752 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 5,824 ms
16,864 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 27 ms
6,944 KB
testcase_08 AC 32 ms
7,440 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 5,713 ms
16,788 KB
testcase_12 AC 1,159 ms
6,940 KB
testcase_13 AC 5,608 ms
16,740 KB
testcase_14 AC 5,656 ms
16,420 KB
testcase_15 AC 483 ms
6,940 KB
testcase_16 AC 1,099 ms
6,944 KB
testcase_17 AC 5,286 ms
15,896 KB
testcase_18 AC 5,370 ms
16,304 KB
testcase_19 AC 11 ms
6,944 KB
testcase_20 AC 12 ms
6,944 KB
testcase_21 AC 72 ms
6,944 KB
testcase_22 AC 2,153 ms
14,104 KB
testcase_23 AC 175 ms
11,884 KB
testcase_24 AC 5 ms
6,940 KB
testcase_25 AC 410 ms
12,724 KB
testcase_26 AC 3 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

template<int mod>
struct ModInt{
	int x;
	ModInt () : x(0) {}
	ModInt (int64_t x) : x(x >= 0 ? x % mod : (mod - -x % mod) % mod) {}
	ModInt &operator += (const ModInt &p){
		if ((x += p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator -= (const ModInt &p) {
		if ((x += mod - p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator *= (const ModInt &p) {
		x = (int64_t) x * p.x % mod;
		return *this;
	}
	ModInt &operator /= (const ModInt &p) {
		*this *= p.inverse();
		return *this;
	}
	ModInt &operator ^= (int64_t p) {
		ModInt res = 1;
		for (; p; p >>= 1) {
			if (p & 1) res *= *this;
			*this *= *this;
		}
		return *this = res;
	}
	ModInt operator - () const { return ModInt(-x); }
	ModInt operator + (const ModInt &p) const { return ModInt(*this) += p; }
	ModInt operator - (const ModInt &p) const { return ModInt(*this) -= p; }
	ModInt operator * (const ModInt &p) const { return ModInt(*this) *= p; }
	ModInt operator / (const ModInt &p) const { return ModInt(*this) /= p; }
	ModInt operator ^ (int64_t p) const { return ModInt(*this) ^= p; }
	bool operator == (const ModInt &p) const { return x == p.x; }
	bool operator != (const ModInt &p) const { return x != p.x; }
	explicit operator int() const { return x; }
	ModInt &operator = (const int p) { x = p; return *this;}
	ModInt inverse() const {
		int a = x, b = mod, u = 1, v = 0, t;
		while (b > 0) {
			t = a / b;
			a -= t * b;
			std::swap(a, b);
			u -= t * v;
			std::swap(u, v);
		}
		return ModInt(u);
	}
	friend std::ostream & operator << (std::ostream &stream, const ModInt<mod> &p) {
		return stream << p.x;
	}
	friend std::istream & operator >> (std::istream &stream, ModInt<mod> &a) {
		int64_t x;
		stream >> x;
		a = ModInt<mod>(x);
		return stream;
	}
};
typedef ModInt<998244353> mint;

template<int mod> struct MComb {
	using mint = ModInt<mod>;
	std::vector<mint> fact;
	std::vector<mint> inv;
	MComb (int n) { // O(n + log(mod))
		fact = std::vector<mint>(n + 1, 1);
		for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * mint(i);
		inv.resize(n + 1);
		inv[n] = fact[n] ^ (mod - 2);
		for (int i = n; i--; ) inv[i] = inv[i + 1] * mint(i + 1);
	}
	mint ncr(int n, int r) {
		return fact[n] * inv[r] * inv[n - r];
	}
	mint npr(int n, int r) {
		return fact[n] * inv[n - r];
	}
	mint nhr(int n, int r) {
		assert(n + r - 1 < (int) fact.size());
		return ncr(n + r - 1, r);
	}
};


int main() {
	int h = ri();
	int w = ri();
	int n = ri();
	
	if (w == 1) {
		if (n != 4) {
			puts("0");
			return 0;
		}
		printf("%d\n", (int) ((int64_t) h * (h + 1) / 2 % 998244353));
		return 0;
	}
	
	std::map<std::pair<std::vector<int>, std::vector<bool> >, int> compress;
	std::vector<std::pair<std::vector<int>, std::vector<bool> > > decompress;
	{
		int cnt = 0;
		std::vector<int> a(w);
		while (1) {
			bool used[w + 1];
			memset(used, 0, sizeof(used));
			used[0] = true;
			
			bool ok = true;
			for (auto i : a) {
				if (std::accumulate(used, used + i, 0) != i) {
					ok = false;
					break;
				}
				used[i] = true;
			}
			if (ok) {
				int all = std::accumulate(used, used + w + 1, 0);
				for (int i = 0; i < 1 << all; i += 2) {
					std::vector<bool> zo(w);
					for (int j = 0; j < w; j++) zo[j] = i >> a[j] & 1;
					compress[{a, zo}] = cnt++;
					decompress.push_back({a, zo});
				}
			}
			
			int head = 0;
			while (head < w && ++a[head] > w) a[head++] = 0;
			if (head >= w) break;
		}
	}
	
	auto normalize = [] (std::vector<int> a) {
		int head = 1;
		int to[20];
		for (auto &i : to) i = -1;
		to[0] = 0;
		
		for (auto &i : a) {
			if (to[i] == -1) to[i] = head++, i = to[i];
			else i = to[i];
		}
		return a;
	};
	
	int s = compress.size();
	mint dp[s][n + 1][2][2]; // state, # of vertex, up, finished
	dp[0][0][0][0] = 1;
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j < w; j++) {
			mint next[s][n + 1][2][2]; // state, # of vertex, up, finished
			for (int k = 0; k < s; k++) {
				auto tmp = decompress[k];
				auto group = tmp.first;
				auto zo = tmp.second;
				auto is_only = [&] (int l) {
					return std::count(group.begin(), group.end(), l) == 1;
				};
				auto comp = [&] (std::vector<int> group, std::vector<bool> zo) {
					assert(compress.count({group, zo}));
					return compress[{group, zo}];
				};
				for (int l = 0; l <= n; l++) {
					for (int m = 0; m < 2; m++) {
						for (int f = 0; f < 2; f++) {
							if (dp[k][l][m][f] == 0) continue;
							do { // don't use
								int next_vertex = l;
								if (j == 0) {
									if (zo[0]) next_vertex++;
									if (next_vertex > n) {}
									else {
										auto next_group = group;
										next_group[0] = 0;
										next_group = normalize(next_group);
										auto next_zo = zo;
										next_zo[0] = false;
										int next_s = comp(next_group, next_zo);
										bool next_f = f;
										if (zo[0] && is_only(group[0])) {
											if (next_zo != std::vector<bool>(w)) break;
											next_f = true;
										}
										next[next_s][next_vertex][zo[0]][next_f] += dp[k][l][m][f];
									}
									// 0
								} else if (j == w - 1) {
									if ((m + zo[j] + zo[j - 1]) & 1) next_vertex++;
									if (zo[j]) next_vertex++;
									if (next_vertex > n) {}
									else {
										auto next_group = group;
										if (!zo[j - 1] && !zo[j]) {
											int r0 = group[j - 1];
											int r1 = group[j];
											for (auto &v : next_group) if (v == r0 || v == r1) v = 0;
										} else if (!zo[j - 1]) {
											int r0 = group[j - 1];
											for (auto &v : next_group) if (v == r0) v = 0;
											next_group[j] = 0;
										} else if (!zo[j]) {
											int r0 = group[j];
											for (auto &v : next_group) if (v == r0) v = 0;
										} else next_group[j] = 0;
										next_group = normalize(next_group);
										
										auto next_zo = zo;
										next_zo[j] = false;
										int next_s = comp(next_group, next_zo);
										bool next_f = f;
										if (zo[j] && is_only(group[j])) {
											if (next_zo != std::vector<bool>(w)) break;
											next_f = true;
										}
										next[next_s][next_vertex][0][next_f] += dp[k][l][m][f];
									}
								} else {
									if ((m + zo[j] + zo[j - 1]) & 1) next_vertex++;
									if (next_vertex > n) {}
									else {
										auto next_group = group;
										if (!zo[j - 1] && !zo[j]) {
											int r0 = group[j - 1];
											int r1 = group[j];
											int r = std::min(r0, r1);
											for (auto &v : next_group) if (v == r0 || v == r1) v = r;
										} else if (!zo[j - 1]) next_group[j] = next_group[j - 1];
										else if (!zo[j]) {}
										else next_group[j] = 19;
										next_group = normalize(next_group);
										
										auto next_zo = zo;
										next_zo[j] = false;
										int next_s = comp(next_group, next_zo);
										bool next_f = f;
										if (zo[j] && is_only(group[j])) {
											if (next_zo != std::vector<bool>(w)) break;
											next_f = true;
										}
										next[next_s][next_vertex][zo[j]][next_f] += dp[k][l][m][f];
									}
								}
							} while (0);
							// ---------------------------
							if (i != h && !f) do {
								int next_vertex = l;
								if (j == 0) {
									if (!zo[0]) next_vertex++;
									if (next_vertex > n) {}
									else {
										auto next_group = group;
										if (!zo[0]) next_group[0] = 19;
										next_group = normalize(next_group);
										auto next_zo = zo;
										next_zo[0] = true;
										int next_s = comp(next_group, next_zo);
										next[next_s][next_vertex][zo[0]][f] += dp[k][l][m][f];
									}
									// 0
								} else if (j == w - 1) {
									if ((m + zo[j] + zo[j - 1] + 1) & 1) next_vertex++;
									if (!zo[j]) next_vertex++;
									if (next_vertex > n) {}
									else {
										auto next_group = group;
										if (zo[j - 1] && zo[j]) {
											int r0 = group[j - 1];
											int r1 = group[j];
											int r = std::min(r0, r1);
											for (auto &v : next_group) if (v == r0 || v == r1) v = r;
										} else if (zo[j - 1]) next_group[j] = next_group[j - 1];
										else if (zo[j]) {}
										else next_group[j] = 19;
										next_group = normalize(next_group);
										
										auto next_zo = zo;
										next_zo[j] = true;
										int next_s = comp(next_group, next_zo);
										if (!zo[j]) assert(!group[j]);
										next[next_s][next_vertex][0][false] += dp[k][l][m][f];
									}
								} else {
									if ((m + zo[j] + zo[j - 1] + 1) & 1) next_vertex++;
									if (next_vertex > n) {}
									else {
										auto next_group = group;
										if (zo[j - 1] && zo[j]) {
											int r0 = group[j - 1];
											int r1 = group[j];
											int r = std::min(r0, r1);
											for (auto &v : next_group) if (v == r0 || v == r1) v = r;
										} else if (zo[j - 1]) next_group[j] = next_group[j - 1];
										else if (zo[j]) {}
										else next_group[j] = 19;
										next_group = normalize(next_group);
										
										auto next_zo = zo;
										next_zo[j] = true;
										int next_s = comp(next_group, next_zo);
										if (!zo[j] && group[j] && is_only(group[j])) break;
										next[next_s][next_vertex][zo[j]][false] += dp[k][l][m][f];
									}
								}
								
							} while (0);
						}
					}
				}
			}
			memcpy(dp, next, sizeof(next));
		}
	}

	std::cout << dp[0][n][0][1] << std::endl;
	
	/*
	for (auto i : states) {
		for (auto j : i.first) std::cerr << j << " ";
		std::cerr << std::endl;
	}*/
	/*
	mint dp[s][1 << w][n + 1];
	dp[0][0][0] = 1;
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j < s; j++) {
			std::vector<int> connection = decompress[j];
			
			for (int k = 0; k < 1 << w; k++) {
				for (int l = 0; l <= n; l++) {
					
				}
			}
			
		}
	}
	*/
	
	
	return 0;
}
0