結果
| 問題 | No.1397 Analog Graffiti |
| ユーザー |
 QCFium
|
| 提出日時 | 2021-02-14 22:31:00 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
#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, finisheddp[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, finishedfor (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 useint 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;}