結果
問題 | No.2384 Permutations of Permutations |
ユーザー |
![]() |
提出日時 | 2023-05-18 00:10:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,742 bytes |
コンパイル時間 | 2,191 ms |
コンパイル使用メモリ | 208,020 KB |
最終ジャッジ日時 | 2025-02-13 01:09:24 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using mint = atcoder::modint998244353; using S6 = std::array<int, 6>; S6 op(S6 x, const S6& y) { for (int i = 0; i < 6; i++) x[i] = y[x[i]]; return x; } S6 inv(const S6& x) { S6 y; for (int i = 0; i < 6; i++) y[x[i]] = i; return y; } mint solve(const int N, const int K) { if (N == 2) { return 1; } if (N != 6) { mint ret = K; for (int i = 1; i <= N - K; i++) ret *= i; return ret; } const S6 id = { {0, 1, 2, 3, 4, 5} }; // one of the outer automorphisms std::map<S6, S6> out; { const std::array<S6, 5> adj = { { {1, 0, 3, 2, 5, 4}, {5, 3, 4, 1, 2, 0}, {3, 2, 1, 0, 5, 4}, {5, 4, 3, 2, 1, 0}, {2, 3, 0, 1, 5, 4}, } }; S6 p = id; do { S6 p_ = p, q = id; for (int i = 0; i < 6; i++) { for (int j = 0; j < 5; j++) { if (p_[j] > p_[j + 1]) { std::swap(p_[j], p_[j + 1]); q = op(q, adj[j]); } } } out[p] = q; } while (std::next_permutation(p.begin(), p.end())); } S6 f = id; std::rotate(f.begin(), f.begin() + 1, f.begin() + K); const auto check = [&](const S6& p) { for (int i = 0; i < K; i++) if (f[i] != p[i]) return false; return true; }; mint ans = 0; { S6 p = id; do { S6 t = op(op(inv(p), f), p); // check inner automorphism if (check(t)) ans += 1; // check outer automorphism if (check(out[t])) ans += 1; } while (std::next_permutation(p.begin(), p.end())); } return ans; } int main() { int N, K; std::cin >> N >> K; std::cout << solve(N, K).val() << "\n"; return 0; }