QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#208708 | #4937. Permutation Transformation | Beevo# | WA | 7ms | 4488kb | C++23 | 1.8kb | 2023-10-09 20:09:40 | 2023-10-09 20:09:41 |
Judging History
answer
#include <bits/stdc++.h>
#define el '\n'
#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 5, M = 998244353;
int mxP[N];
int add(int a, int b) {
return (a + b) % M;
}
int mul(int a, int b) {
return 1LL * a * b % M;
}
int modPow(int b, int p) {
if (p == 0)
return 1;
int x = modPow(b, p / 2);
return p % 2 == 0 ? mul(x, x) : mul(b, mul(x, x));
}
void testCase() {
int n;
cin >> n;
int p[n + 1];
for (int i = 1; i <= n; i++)
cin >> p[i];
int mx = 0;
vector<bool> vis(n + 1);
for (int i = 1; i <= n; i++) {
if (vis[p[i]])
continue;
vis[p[i]] = 1;
deque<int> d = {p[i]};
while (p[d.back()] != d[0])
d.push_back(p[d.back()]), vis[d.back()] = 1;
int cnt = 0;
for (int j = 0; j < d.size() && d[0] != i; j++)
d.push_back(d[0]), d.pop_front(), cnt++;
if (d[0] == i && is_sorted(d.begin(), d.end()))
mx = max(mx, cnt);
else {
int sz = d.size(), cur = sz / 2;
if (sz & 1)
cur = sz - 1;
for (int j = 2; j * j <= cur; j++) {
int curCnt = 0;
while (cur % j == 0)
curCnt++, cur /= j;
mxP[j] = max(mxP[j], curCnt);
}
mxP[cur] = max(mxP[cur], 1);
}
}
int l = 1;
for (int i = 2; i < N; i++)
l = mul(l, modPow(i, mxP[i]));
cout << add(mx, l);
}
signed main() {
Beevo
int t = 1;
// cin >> t;
while (t--)
testCase();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3732kb
input:
5 3 5 1 2 4
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
8 7 5 1 6 8 2 3 4
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
1 1
output:
1
result:
ok single line: '1'
Test #4:
score: -100
Wrong Answer
time: 7ms
memory: 4488kb
input:
100000 20864 34918 58550 1465 75674 30743 27235 88900 47488 50029 46054 84871 20330 72228 16506 44561 92519 97750 82891 60324 90508 39290 24663 38077 90189 30671 95476 64027 70888 90749 22566 8525 33675 16635 23392 97636 35788 89625 41966 78051 94034 15407 26545 83799 2233 10873 56946 71566 19045 44...
output:
711479533
result:
wrong answer 1st lines differ - expected: '216333199', found: '711479533'