QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#615044 | #5547. Short Function | Oldera# | WA | 0ms | 3708kb | C++14 | 1.9kb | 2024-10-05 17:28:44 | 2024-10-05 17:28:49 |
Judging History
answer
/*
www.youtube.com/YugiHackerChannel
linktr.ee/YugiHacker
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 100005
#define int long long
#define MOD 998244353
using namespace std;
int n, k, a[maxn];
long long P = 1, I = 1, R, X = 0;
long long Pow(long long a, long long n)
{
a %= MOD;
long long ans = 1;
for (;n;n/=2, a=a*a%MOD) if (n&1) (ans *= a) %= MOD;
return ans;
}
void solve(int k) {
if (k == 0) {
R = 1;
X = 0;
return;
}
solve(k/2);
X = (X * X % (MOD - 1) * n % (MOD - 1) + 2 * X * R + R * R / n) % (MOD - 1);
R = R * R % n;
if (k & 1) {
X = (X * 2 + R * 2 / n) % (MOD - 1);
R = R * 2 % n;
}
}
void calc() {
long long r = 1;
while (k) {
I = I * I % MOD * Pow(P, n) % MOD;
r = r * r;
if (k & 1) r *= 2;
int x = r / n;
r %= n;
if (r == 0) r = n, x--;
I = I * Pow(P, x) % MOD;
k /= 2;
}
// for (int i=0; i<k; i++) {
// I = I * I % MOD;
// r *= 2;
// if (r > n) I = I * P % MOD, r -= n;
// }
R = r;
}
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
cin >> n >> k;
f0 (i, n) cin >> a[i], (P *= a[i]) %= MOD;
long long cur = 1;
solve(k);
I = Pow(P, X);
for (int i=0; i<R-1; i++) {
cur *= a[i];
}
///cout << X << ' ' << R << ' ' << I <<' ' << cur, el;
if (R == 0) {
for (int i=0; i<n; i++) cout << I << ' ';
return 0;
}
for (int i=0; i<n; i++) {
cur *= a[(i+R-1)%n];
cur %= MOD;
cout << cur * I % MOD << ' ';
cur = cur * Pow(a[i], MOD - 2) % MOD;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3708kb
input:
5 2 1 2 3 4 5
output:
24 120 60 40 30
result:
ok 5 number(s): "24 120 60 40 30"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
8 3 12 5 16 14 10 6 9 2
output:
14515200 14515200 14515200 14515200 14515200 14515200 14515200 14515200
result:
ok 8 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
6 10 3 7 8 2 9 5
output:
56347321 169041963 833775940 811788154 844769833 639990479
result:
ok 6 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2 100 1 2
output:
917380677 917380677
result:
ok 2 number(s): "917380677 917380677"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3704kb
input:
119 1000000000 179906895 883175111 831258723 617910763 41850684 952649819 667608052 992898634 871657688 261948841 858714230 452797779 698675390 39373823 268148685 762575950 789163136 676908074 134428624 583625412 549545785 415007638 564283552 596519552 575204092 884934270 632550339 21505752 66058955...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 1st numbers differ - expected: '375116230', found: '0'