結果
問題 | No.2428 Returning Shuffle |
ユーザー |
|
提出日時 | 2023-08-19 00:33:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 233 ms / 2,000 ms |
コード長 | 1,174 bytes |
コンパイル時間 | 2,253 ms |
コンパイル使用メモリ | 205,712 KB |
最終ジャッジ日時 | 2025-02-16 11:12:35 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll=long long;constexpr int mod=998244353;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N,M;cin>>N>>M;vector<int>P(N);iota(P.begin(),P.end(),0);for(int i=0;i<M;i++){int T;cin>>T;vector<int>A(T);for(int &j:A)cin>>j,--j;int p=P[A[T-1]];for(int j=T-2;j>=0;j--){P[A[j+1]]=P[A[j]];}P[A[0]]=p;}vector<int>prime(N+1,-1);for(int i=2;i<=N;i++){if(prime[i]!=-1)continue;for(int j=i*2;j<=N;j+=i){prime[j]=i;}}vector<bool>vst(N);map<int,int>lcm_cnt;for(int i=0;i<N;i++){if(vst[i])continue;int cnt=1,t=P[i];vst[i]=1;while(t!=i){vst[t]=1;cnt+=1;t=P[t];}map<int,int>n_prime;while(cnt>1){if(prime[cnt]!=-1){n_prime[prime[cnt]]+=1;cnt/=prime[cnt];}else{n_prime[cnt]+=1;cnt/=cnt;}}for(auto j:n_prime){lcm_cnt[j.first]=max(lcm_cnt[j.first],j.second);}}ll ans=1;for(auto i:lcm_cnt){for(int j=0;j<i.second;j++){ans=ans*i.first%mod;}}cout<<ans<<'\n';}