結果
問題 | No.2428 Returning Shuffle |
ユーザー |
|
提出日時 | 2023-08-18 21:51:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 682 ms / 2,000 ms |
コード長 | 1,001 bytes |
コンパイル時間 | 4,370 ms |
コンパイル使用メモリ | 260,560 KB |
最終ジャッジ日時 | 2025-02-16 09:54:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using mint = atcoder::modint998244353; using namespace std; int main() { int N, M; cin >> N >> M; vector<int> A(N); iota(A.begin(), A.end(), 0); for (int i = 0; i < M; i++){ int T; cin >> T; vector<int> S(T); for (int j = 0; j < T; j++){ cin >> S[j]; S[j]--; } vector<int> B(T); for (int j = 0; j < T; j++){ B[j] = A[S[j]]; } for (int j = 0; j < T; j++){ A[S[j]] = B[(j - 1 + T) % T]; } } atcoder::dsu uf(N); for (int i = 0; i < N; i++){ uf.merge(i, A[i]); } mint ans = 1; map<int, int> p; for (auto s : uf.groups()){ int k = s.size(); vector<int> C(k + 1); for (int i = 2; i <= k; i++){ for (int j = i; j <= k; j += i){ C[j]++; } } for (int i = 2; i <= k; i++){ if (C[i] == 1){ int k2 = k; int c = 0; while (k2 % i == 0){ k2 /= i; c++; } p[i] = max(p[i], c); } } } for (auto [k, v] : p){ ans *= mint(k).pow(v); } cout << ans.val() << '\n'; }