QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#615044#5547. Short FunctionOldera#WA 0ms3708kbC++141.9kb2024-10-05 17:28:442024-10-05 17:28:49

Judging History

你现在查看的是最新测评结果

  • [2024-10-05 17:28:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3708kb
  • [2024-10-05 17:28:44]
  • 提交

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'