結果
| 問題 | No.2668 Trees on Graph Paper |
| ユーザー |
 suisen
|
| 提出日時 | 2023-12-28 05:20:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,774 bytes |
| コンパイル時間 | 1,181 ms |
| コンパイル使用メモリ | 91,800 KB |
| 最終ジャッジ日時 | 2025-02-18 14:48:35 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 MLE * 1 -- * 29 |
ソースコード
// naive#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 {while(1);}}