結果

問題 No.2428 Returning Shuffle
ユーザー bortik
提出日時 2023-08-19 01:52:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 438 ms / 2,000 ms
コード長 1,586 bytes
コンパイル時間 2,029 ms
コンパイル使用メモリ 208,384 KB
最終ジャッジ日時 2025-02-16 11:19:18
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#define ll long long
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++){
int x; cin >> x;
s[j] = x-1;
}
int p = s[0];
for(int k = 1; k < t; k++){
swap(a[s[k]], a[p]);
}
}
vector<int> l;
vector<bool> seen(n, false);
for(int i = 0; i < n; i++){
if(seen[i]) continue;
seen[i] = true;
int cur = a[i];
int len = 1;
while(cur != i){
len++;
seen[cur] = true;
cur = a[cur];
}
l.push_back(len);
}
map<ll,ll> lcm;
ll answer = 1;
vector<bool> primes(1001, true);
primes[0] = false;
primes[1] = false;
for(int i = 2; i < 1001;i++) if (primes[i]){
for(int j = 2*i; j < 1001; j += i) primes[j] = false;
}
for(ll x: l){
map<ll,ll> cur;
ll e = x;
ll root = sqrt(x);
for(int i = 2; i <= root; i++) {
if(primes[i]){
while(e % i == 0) {
cur[i]++;
e /= i;
}
}
}
cur[e]++;
for(auto& i: cur) if(lcm[i.first] < i.second) lcm[i.first] = i.second;
}
for(auto& i: lcm){
for(ll j = 0; j < i.second; j++){
answer = (answer*i.first) % 998244353;
}
}
cout << answer;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0