結果
問題 | No.2428 Returning Shuffle |
ユーザー |
|
提出日時 | 2023-08-18 21:49:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 174 ms / 2,000 ms |
コード長 | 979 bytes |
コンパイル時間 | 621 ms |
コンパイル使用メモリ | 72,432 KB |
実行使用メモリ | 16,384 KB |
最終ジャッジ日時 | 2024-11-28 06:35:52 |
合計ジャッジ時間 | 3,224 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include<iostream>#include<algorithm>#include<vector>#include<cassert>#include<atcoder/modint>using namespace std;int N,M;int P[1<<20];int S[1<<20];bool vis[1<<20];int lsp[1<<20];int cnt[1<<20];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);for(int i=2;i<1<<20;i++)if(lsp[i]==0){for(int j=i;j<1<<20;j+=i)lsp[j]=i;}cin>>N>>M;for(int i=0;i<N;i++)P[i]=i;for(;M--;){int T;cin>>T;for(int i=0;i<T;i++){cin>>S[i];S[i]--;}int cur=P[S[T-1]];for(int i=T-1;i--;){P[S[i+1]]=P[S[i]];}P[S[0]]=cur;//for(int i=0;i<N;i++)cout<<P[i]<<" ";cout<<endl;}for(int i=0;i<N;i++)if(!vis[i]){int u=i,sz=0;while(!vis[u]){vis[u]=true;u=P[u];sz++;}while(sz>1){int p=lsp[sz],c=0;while(sz%p==0)sz/=p,c++;cnt[p]=max(cnt[p],c);}}using mint=atcoder::modint998244353;mint ans=1;for(int i=2;i<1<<20;i++)if(cnt[i]>0)ans*=mint::raw(i).pow(cnt[i]);cout<<ans.val()<<endl;}