結果
| 問題 | No.2668 Trees on Graph Paper |
| ユーザー |
 suisen
|
| 提出日時 | 2023-12-28 05:21:02 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,769 bytes |
| コンパイル時間 | 1,248 ms |
| コンパイル使用メモリ | 94,940 KB |
| 実行使用メモリ | 814,128 KB |
| 最終ジャッジ日時 | 2024-09-28 17:42:57 |
| 合計ジャッジ時間 | 6,196 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 23 ms
6,816 KB |
| testcase_02 | AC | 2,162 ms
6,816 KB |
| testcase_03 | MLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
ソースコード
#include <cassert>
#include <deque>
#include <iostream>
#include <utility>
#include <vector>
#include <atcoder/modint>
int sgn(int x) {
return x == 0 ? 0 : x > 0 ? +1 : -1;
}
bool intersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
int d3 = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
int d4 = (x2 - x1) * (y4 - y1) - (y2 - y1) * (x4 - x1);
int d1 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);
int d2 = (x4 - x3) * (y2 - y3) - (y4 - y3) * (x2 - x3);
return sgn(d1) * sgn(d2) < 0 and sgn(d3) * sgn(d4) < 0;
}
int main() {
int n, m;
std::cin >> n >> m;
using mint = atcoder::modint;
mint::set_mod(m);
std::vector<std::pair<int, int>> points;
for (int x = 1; x <= 2 * n; ++x) {
for (int y = 1; x + y <= 2 * n; ++y) {
if ((x + y) % 2 == 0) points.emplace_back(x, y);
}
}
const int k = points.size();
assert(k == n * n);
if (n <= 3) {
std::vector<std::pair<int, int>> edges;
for (int i = 0; i < k; ++i) for (int j = i + 1; j < k; ++j) {
auto [xi, yi] = points[i];
auto [xj, yj] = points[j];
if (::abs(xi - xj) + ::abs(yi - yj) == 2) {
edges.emplace_back(i, j);
}
}
const int l = edges.size();
std::vector<int> ng_subset;
for (int i = 0; i < l; ++i) for (int j = i + 1; j < l; ++j) {
auto [a, b] = edges[i];
auto [c, d] = edges[j];
auto [xa, ya] = points[a];
auto [xb, yb] = points[b];
auto [xc, yc] = points[c];
auto [xd, yd] = points[d];
if (intersect(xa, ya, xb, yb, xc, yc, xd, yd)) {
ng_subset.push_back((1 << i) | (1 << j));
}
}
mint ans = 0;
for (int s = 0; s < 1 << l; ++s) {
if (__builtin_popcount(s) != k - 1) {
continue;
}
bool ok = true;
for (int ng : ng_subset) {
if ((ng & s) == ng) {
ok = false;
break;
}
}
if (not ok) {
continue;
}
std::vector<std::vector<int>> g(k);
for (int i = 0; i < l; ++i) if ((s >> i) & 1) {
auto [u, v] = edges[i];
g[u].push_back(v);
g[v].push_back(u);
}
int cnt = 0;
std::vector<int> dist(k, -1);
dist[0] = 0;
std::deque<int> dq{ 0 };
while (dq.size()) {
int u = dq.front();
dq.pop_front();
auto [x, y] = points[u];
++cnt;
if (dist[u] != (x + y) / 2 - 1) {
ok = false;
break;
}
for (int v : g[u]) if (dist[v] == -1) {
dist[v] = dist[u] + 1;
dq.push_back(v);
}
}
ok &= cnt == k;
if (not ok) {
continue;
}
mint w = 1;
for (int i = 0; i < k; ++i) if (g[i].size() == 1) {
w *= points[i].first;
}
ans += w;
}
std::cout << ans.val() << std::endl;
} else if (n == 4) {
std::vector<std::pair<int, int>> edges;
for (int i = 0; i < k; ++i) for (int j = i + 1; j < k; ++j) {
auto [xi, yi] = points[i];
auto [xj, yj] = points[j];
if (::abs(xi - xj) + ::abs(yi - yj) == 2 and xi + yi != xj + yj) {
edges.emplace_back(i, j);
}
}
const int l = edges.size();
std::vector<int> ng_subset;
for (int i = 0; i < l; ++i) for (int j = i + 1; j < l; ++j) {
auto [a, b] = edges[i];
auto [c, d] = edges[j];
auto [xa, ya] = points[a];
auto [xb, yb] = points[b];
auto [xc, yc] = points[c];
auto [xd, yd] = points[d];
if (intersect(xa, ya, xb, yb, xc, yc, xd, yd)) {
ng_subset.push_back((1 << i) | (1 << j));
}
}
mint ans = 0;
for (int s = 0; s < 1 << l; ++s) {
if (__builtin_popcount(s) != k - 1) {
continue;
}
bool ok = true;
for (int ng : ng_subset) {
if ((ng & s) == ng) {
ok = false;
break;
}
}
if (not ok) {
continue;
}
std::vector<std::vector<int>> g(k);
for (int i = 0; i < l; ++i) if ((s >> i) & 1) {
auto [u, v] = edges[i];
g[u].push_back(v);
g[v].push_back(u);
}
int cnt = 0;
std::vector<int> dist(k, -1);
dist[0] = 0;
std::deque<int> dq{ 0 };
while (dq.size()) {
int u = dq.front();
dq.pop_front();
auto [x, y] = points[u];
++cnt;
if (dist[u] != (x + y) / 2 - 1) {
ok = false;
break;
}
for (int v : g[u]) if (dist[v] == -1) {
dist[v] = dist[u] + 1;
dq.push_back(v);
}
}
ok &= cnt == k;
if (not ok) {
continue;
}
mint w = 1;
for (int i = 0; i < k; ++i) if (g[i].size() == 1) {
w *= points[i].first;
}
ans += w;
}
std::cout << ans.val() << std::endl;
} else if (n <= 9) {
mint ans = 1;
for (int t = 1; t < n; ++t) {
mint sumw = 0;
const int l = 4 * (t - 1);
for (int s = 0; s < 1 << l; ++s) {
if (s & (s >> 1)) continue;
std::vector<int> c(2 * t - 1);
for (int i = 1; i <= 2 * t - 3; ++i) {
c[i] += (s >> (2 * i - 2)) & 1;
c[i] += (s >> (2 * i + 1)) & 1;
c[i] += ((s >> (2 * i - 1)) & 1) == 0 and ((s >> (2 * i)) & 1) == 0;
}
mint w = 1;
for (int i = 1; i <= 2 * t - 3; ++i) {
if (c[i] == 0) {
w *= i + 1;
}
}
sumw += w;
}
ans *= sumw;
}
for (int i = 1; i <= 2 * n - 1; ++i) {
ans *= i;
}
std::cout << ans.val() << std::endl;
} else {
assert(false);
}
}