QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#175810 | #6417. Classical Summation Problem | danielkou5855 | WA | 1ms | 3504kb | C++17 | 1.2kb | 2023-09-11 00:32:22 | 2023-09-11 00:32:22 |
Judging History
answer
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD = 998244353;
ll exp(ll a, ll b) {
ll res = 1;
while (b > 0) {
if (b & 1)
res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
vector<ll> factorial;
void generate_factorial(int m) {
factorial.resize(m + 1);
factorial[0] = 1;
for (ll i = 1; i <= m; i++) {
factorial[i] = factorial[i - 1] * i; factorial[i] += MOD; factorial[i] %= MOD;
}
}
ll choose(ll a, ll b) {
ll tmp = factorial[a];
tmp *= exp(factorial[a - b], MOD - 2); tmp += MOD; tmp %= MOD;
tmp *= exp(factorial[b], MOD - 2); tmp += MOD; tmp %= MOD;
return tmp;
}
signed main() {
int N, K; cin >> N >> K;
generate_factorial(max(N + 1, K));
if (K % 2 == 1) {
ll ans = ((N + 1) / 2) * exp(N, K) % MOD;
cout << ans << "\n";
return 0;
}
ll ans = 0;
for (int i = 1; i < N; i++) {
ll tmp = choose(K, K / 2) * exp(i, K / 2) % MOD;
tmp = tmp * exp(N - i + 1, K / 2) % MOD;
ans += tmp;
}
cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3504kb
input:
3 2
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
5 3
output:
375
result:
ok 1 number(s): "375"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3376kb
input:
2 2
output:
4
result:
wrong answer 1st numbers differ - expected: '5', found: '4'