結果
問題 | No.2428 Returning Shuffle |
ユーザー | pengin_2000 |
提出日時 | 2023-08-18 22:46:50 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 590 ms / 2,000 ms |
コード長 | 1,558 bytes |
コンパイル時間 | 896 ms |
コンパイル使用メモリ | 30,244 KB |
実行使用メモリ | 35,012 KB |
最終ジャッジ日時 | 2023-08-18 22:46:56 |
合計ジャッジ時間 | 5,336 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 122 ms
28,368 KB |
testcase_01 | AC | 590 ms
35,012 KB |
testcase_02 | AC | 560 ms
34,820 KB |
testcase_03 | AC | 2 ms
10,096 KB |
testcase_04 | AC | 2 ms
9,932 KB |
testcase_05 | AC | 3 ms
9,976 KB |
testcase_06 | AC | 2 ms
9,900 KB |
testcase_07 | AC | 3 ms
9,984 KB |
testcase_08 | AC | 2 ms
10,008 KB |
testcase_09 | AC | 2 ms
10,104 KB |
testcase_10 | AC | 3 ms
10,044 KB |
testcase_11 | AC | 3 ms
10,076 KB |
testcase_12 | AC | 2 ms
10,072 KB |
testcase_13 | AC | 3 ms
9,940 KB |
testcase_14 | AC | 2 ms
9,904 KB |
testcase_15 | AC | 3 ms
9,884 KB |
testcase_16 | AC | 3 ms
9,996 KB |
testcase_17 | AC | 3 ms
9,988 KB |
testcase_18 | AC | 3 ms
9,996 KB |
testcase_19 | AC | 252 ms
32,552 KB |
testcase_20 | AC | 238 ms
32,508 KB |
testcase_21 | AC | 2 ms
9,900 KB |
testcase_22 | AC | 2 ms
9,968 KB |
testcase_23 | AC | 2 ms
9,984 KB |
testcase_24 | AC | 245 ms
28,452 KB |
testcase_25 | AC | 246 ms
28,532 KB |
ソースコード
#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; }