QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121573 | #6417. Classical Summation Problem | SolitaryDream# | WA | 16ms | 15524kb | C++20 | 1.2kb | 2023-07-08 14:45:50 | 2023-07-08 14:45:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int p = 998244353;
const int inv2 = (p + 1) >> 1;
int n, m, fac[N], finv[N], inv[N];
inline int Qpow(int x, int y = p - 2) {
int ans = 1;
for (; y; y >>= 1, x = 1ll * x * x % p)
if (y & 1) ans = 1ll * ans * x % p;
return ans;
}
inline int C(int x, int y) {
if (x < 0 || x < y) return 0;
return 1ll * fac[x] * finv[y] % p * finv[x - y] % p;
}
int main() {
fac[0] = 1; for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % p;
inv[0] = inv[1] = 1; for (int i = 2; i < N; ++i) inv[i] = 1ll * inv[p % i] * (p - p / i) % p;
finv[0] = 1; for (int i = 1; i < N; ++i) finv[i] = 1ll * finv[i - 1] * inv[i] % p;
scanf("%d%d", &n, &m);
int ans = 1ll * Qpow(n, m) * (n + 1) % p * inv2 % p;
if (m % 2 == 0) {
int u = m / 2;
int sm = 0;
int mid = 1ll * (n + 1) * inv2 % p;
for (int i = 1; i <= n; ++i) {
sm = (sm + 1ll * (i - mid) * C(i + u - 1, u - 1) % p * C(n - i + u - 1, u)) % p;
}
ans = (ans + 1ll * C(m, u) * sm) % p;
if (ans < 0) ans += p;
}
printf("%d\n", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 15ms
memory: 15524kb
input:
3 2
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 14ms
memory: 15292kb
input:
5 3
output:
375
result:
ok 1 number(s): "375"
Test #3:
score: 0
Accepted
time: 16ms
memory: 15292kb
input:
2 2
output:
5
result:
ok 1 number(s): "5"
Test #4:
score: 0
Accepted
time: 15ms
memory: 15292kb
input:
10 9
output:
508778235
result:
ok 1 number(s): "508778235"
Test #5:
score: 0
Accepted
time: 12ms
memory: 15292kb
input:
69 3
output:
11497815
result:
ok 1 number(s): "11497815"
Test #6:
score: 0
Accepted
time: 15ms
memory: 15392kb
input:
994 515
output:
33689623
result:
ok 1 number(s): "33689623"
Test #7:
score: -100
Wrong Answer
time: 3ms
memory: 15392kb
input:
4476 6182
output:
683533843
result:
wrong answer 1st numbers differ - expected: '114894183', found: '683533843'