結果
| 問題 | No.1397 Analog Graffiti |
| ユーザー |
 QCFium
|
| 提出日時 | 2021-02-14 22:31:00 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 4,959 ms / 10,000 ms |
| コード長 | 9,854 bytes |
| コンパイル時間 | 3,586 ms |
| コンパイル使用メモリ | 200,932 KB |
| 実行使用メモリ | 16,584 KB |
| 最終ジャッジ日時 | 2023-09-29 16:14:30 |
| 合計ジャッジ時間 | 43,294 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | AC | 2 ms
4,376 KB |
| testcase_02 | AC | 4,870 ms
16,556 KB |
| testcase_03 | AC | 2 ms
4,376 KB |
| testcase_04 | AC | 2 ms
4,376 KB |
| testcase_05 | AC | 4,863 ms
16,516 KB |
| testcase_06 | AC | 1 ms
4,376 KB |
| testcase_07 | AC | 26 ms
6,272 KB |
| testcase_08 | AC | 29 ms
7,092 KB |
| testcase_09 | AC | 1 ms
4,376 KB |
| testcase_10 | AC | 1 ms
4,376 KB |
| testcase_11 | AC | 4,723 ms
16,584 KB |
| testcase_12 | AC | 993 ms
5,672 KB |
| testcase_13 | AC | 4,959 ms
16,560 KB |
| testcase_14 | AC | 4,564 ms
16,072 KB |
| testcase_15 | AC | 468 ms
6,220 KB |
| testcase_16 | AC | 995 ms
5,552 KB |
| testcase_17 | AC | 4,118 ms
15,576 KB |
| testcase_18 | AC | 4,165 ms
16,032 KB |
| testcase_19 | AC | 9 ms
4,376 KB |
| testcase_20 | AC | 10 ms
4,376 KB |
| testcase_21 | AC | 60 ms
4,376 KB |
| testcase_22 | AC | 1,676 ms
13,792 KB |
| testcase_23 | AC | 137 ms
11,716 KB |
| testcase_24 | AC | 4 ms
4,376 KB |
| testcase_25 | AC | 317 ms
12,464 KB |
| testcase_26 | AC | 2 ms
4,376 KB |
ソースコード
#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;
}