結果
問題 | No.2428 Returning Shuffle |
ユーザー |
![]() |
提出日時 | 2023-08-18 22:46:50 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 580 ms / 2,000 ms |
コード長 | 1,558 bytes |
コンパイル時間 | 1,566 ms |
コンパイル使用メモリ | 30,592 KB |
実行使用メモリ | 33,152 KB |
最終ジャッジ日時 | 2024-11-28 08:58:29 |
合計ジャッジ時間 | 4,116 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include<stdio.h>long long int modpow(long long int a, long long int n, long long int p){long long int res = 1;for (; n > 0; n /= 2, a = a * a % p)if (n % 2 > 0)res = res * a % p;return res;}long long int minprime(long long int n){long long int i;for (i = 2; i * i <= n; i++)if (n % i == 0)return i;return n;}long long int t[500005], s[1000006];long long int p[1000006];long long int used[1000006];long long int cyc[1000006], cc;int main(){long long int n, m;scanf("%lld %lld", &n, &m);t[0] = 0;long long int i, j, k;for (i = 0; i < m; i++){scanf("%lld", &t[i + 1]);t[i + 1] += t[i];for (j = t[i]; j < t[i + 1]; j++){scanf("%lld", &s[j]);s[j]--;}}for (i = 0; i < n; i++)p[i] = i;for (i = 0; i < m; i++){k = p[s[t[i + 1] - 1]];for (j = t[i + 1] - 1; j > t[i]; j--)p[s[j]] = p[s[j - 1]];p[s[t[i]]] = k;}long long int cnt;const long long int prime = 998244353;for (i = 0; i < n; i++)used[i] = 0;cc = 0;for (i = 0; i < n; i++){if (used[i] > 0)continue;for (j = i, cnt = 0; used[j] == 0; j = p[j]){used[j]++;cnt++;}cyc[cc] = cnt;cc++;}long long int ans = 1;long long int max;for (i = 0; i < cc; i++){while (cyc[i] > 1){j = minprime(cyc[i]);max = 0;for (k = i; k < cc; k++){cnt = 0;while (cyc[k] % j == 0){cnt++;cyc[k] /= j;}if (max < cnt)max = cnt;}ans = ans * modpow(j, max, prime) % prime;}}printf("%lld\n", ans);return 0;}