結果
問題 | No.2428 Returning Shuffle |
ユーザー |
![]() |
提出日時 | 2023-08-13 13:36:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 486 ms / 2,000 ms |
コード長 | 2,086 bytes |
コンパイル時間 | 2,092 ms |
コンパイル使用メモリ | 211,204 KB |
最終ジャッジ日時 | 2025-02-16 07:44:52 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; int main(void){ //cin.tie(nullptr); //ios::sync_with_stdio(false); long long N,M; cin >> N >> M; vector<vector<long long>> S(M); for(int i=0;i<M;i++){ long long t; cin >> t; S[i].resize(t); for(int j=0;j<t;j++){ cin >> S[i][j]; S[i][j]--; } } //置換を作成する vector<long long> F(N); for(int i=0;i<N;i++){F[i] = i;} vector<long long> inverse = F; for(int i=0;i<M;i++){ int s = S[i].size(); for(int j=0;j+1<s;j++){ F[inverse[S[i][j]]] = S[i][j+1]; } F[inverse[S[i][s-1]]] = S[i][0]; long long tmp = inverse[S[i][s-1]]; for(int j=s-2;j>=0;j--){ inverse[S[i][j+1]] = inverse[S[i][j]]; } inverse[S[i][0]] = tmp; } //サイクルの個数を考える vector<bool> visited(N,false); vector<long long> C; for(int i=0;i<N;i++){ if(visited[i])continue; long long now = F[i], num = 1; visited[i] = true; while(now!=i){ visited[now] = true; now = F[now]; num++; } C.push_back(num); } //CのLCMを求める map<long long,long long> Map; for(long long c:C){ vector<pair<long long,long long>> E; long long k = c; for(int i=2;i*i<=c;i++){ if(k%i==0){ E.push_back({i,0}); } while(k%i==0){ k/=i; E.back().second++; } } if(k!=1){ E.push_back({k,1}); } for(pair<long long,long long> p:E){ Map[p.first] = max(Map[p.first],p.second); } } long long Ans = 1; for(auto it = Map.begin();it!=Map.end();it++){ for(int i=0;i<(it->second);i++){ Ans = (Ans*(it->first))%MOD; } } //答えを出力する cout << Ans << endl; return 0; }