QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177755#6417. Classical Summation ProblemduckierWA 8ms11536kbC++141015b2023-09-13 12:38:532023-09-13 12:38:55

Judging History

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

  • [2023-09-13 12:38:55]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:11536kb
  • [2023-09-13 12:38:53]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int M = 998244353;
int n, k, fact[1000001];

int pow2(int a, int b) {
    if(b==0) return 1;
    int c = pow2(a, b/2);
    c = (c*c)%M;
    if(b%2==1) c = (c*a)%M;
    return c;
}

int inv(int a) {
    return pow2(a, M-2);
}

int choose(int a, int b) {
    return (((fact[a] * inv(fact[b]))%M) * inv(fact[a-b]))%M;
}

int mod(int a) {
    return (a%M + M)%M;
}

signed main() {
    fact[0] = 1;
    for(int i = 1; i <= 1000000; i++) fact[i] = (fact[i-1] * i)%M;
    cin>>n>>k;
    if(k%2==1) {
        int ans = pow2(n, k);
        ans = ((ans * (n+1))%M * inv(2))%M;
        cout << ans << '\n';
        return 0;
    }
    int ans =0;
    for(int i= 1; i <= n; i++) {
        ans += (((i * choose(k, k/2))%M * (mod(pow2(i, k/2) - pow2(i-1, k/2))))%M * pow2(n - i, k/2))%M;
    }
    ans %= M;
    k--;
    ans += ((pow2(n, k) * (n+1))%M * inv(2))%M;
    ans %= M;
    cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 11464kb

input:

3 2

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: 0
Accepted
time: 6ms
memory: 11536kb

input:

5 3

output:

375

result:

ok 1 number(s): "375"

Test #3:

score: 0
Accepted
time: 6ms
memory: 11452kb

input:

2 2

output:

5

result:

ok 1 number(s): "5"

Test #4:

score: 0
Accepted
time: 6ms
memory: 11528kb

input:

10 9

output:

508778235

result:

ok 1 number(s): "508778235"

Test #5:

score: 0
Accepted
time: 3ms
memory: 11480kb

input:

69 3

output:

11497815

result:

ok 1 number(s): "11497815"

Test #6:

score: 0
Accepted
time: 0ms
memory: 11456kb

input:

994 515

output:

33689623

result:

ok 1 number(s): "33689623"

Test #7:

score: -100
Wrong Answer
time: 8ms
memory: 11468kb

input:

4476 6182

output:

216647822

result:

wrong answer 1st numbers differ - expected: '114894183', found: '216647822'