QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#177757 | #6417. Classical Summation Problem | duckier | WA | 7ms | 11392kb | C++14 | 1015b | 2023-09-13 12:40:47 | 2023-09-13 12:40:47 |
Judging History
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';
}
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 11168kb
input:
3 2
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 7ms
memory: 11252kb
input:
5 3
output:
375
result:
ok 1 number(s): "375"
Test #3:
score: 0
Accepted
time: 7ms
memory: 11392kb
input:
2 2
output:
5
result:
ok 1 number(s): "5"
Test #4:
score: 0
Accepted
time: 3ms
memory: 11232kb
input:
10 9
output:
508778235
result:
ok 1 number(s): "508778235"
Test #5:
score: 0
Accepted
time: 0ms
memory: 11184kb
input:
69 3
output:
11497815
result:
ok 1 number(s): "11497815"
Test #6:
score: 0
Accepted
time: 7ms
memory: 11116kb
input:
994 515
output:
33689623
result:
ok 1 number(s): "33689623"
Test #7:
score: -100
Wrong Answer
time: 4ms
memory: 11232kb
input:
4476 6182
output:
216647822
result:
wrong answer 1st numbers differ - expected: '114894183', found: '216647822'