QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#106727 | #6417. Classical Summation Problem | hongrock | WA | 2ms | 3544kb | C++17 | 1.6kb | 2023-05-18 22:02:17 | 2023-05-18 22:02:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for(int i=(a); i<(n); ++i)
#define per(i, a, n) for(int i=(a); i>(n); --i)
#define pb emplace_back
#define mp make_pair
#define clr(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(),(x).end()
#define lowbit(x) (x & -x)
#define fi first
#define se second
#define lson o<<1
#define rson o<<1|1
#define gmid l[o]+r[o]>>1
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll, ll>;
using ui = unsigned int;
constexpr int mod = 998244353;
constexpr int inf = 0x3f3f3f3f;
constexpr double EPS = 1e-8;
const double PI = acos(-1.0);
constexpr int N = 1e6 + 10;
ll pow_mod(ll x, int p){
ll s = 1;
while(p){
if(p & 1) s = s * x % mod;
x = x * x % mod;
p >>= 1;
}
return s;
}
int n, k;
ll fac[N], rev[N];
ll C(int n, int m){
return fac[n] * rev[m] % mod * rev[n - m] % mod;
}
void _main(){
cin >> n >> k;
ll e = 0;
e = (1 + n) * pow_mod(2, mod - 2) % mod;
if(k % 2 == 0){
fac[0] = 1;
rep(i, 1, n + 1) fac[i] = fac[i-1] * i % mod;
rev[n] = pow_mod(fac[n], mod - 2);
per(i, n, 0) rev[i-1] = rev[i] * i % mod;
ll d = 0;
rep(i, 1, n){
d = d + pow_mod(i, k / 2) * pow_mod(n - i, k / 2) % mod;
}
d = d % mod * C(k, k / 2) % mod * pow_mod(pow_mod(n, mod - 2), k) % mod;
d = d * pow_mod(2, mod - 2) % mod;
e = (e + mod - d) % mod;
}
cout << e * pow_mod(n, k) % mod << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
_main();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3352kb
input:
3 2
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3384kb
input:
5 3
output:
375
result:
ok 1 number(s): "375"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3308kb
input:
2 2
output:
5
result:
ok 1 number(s): "5"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3384kb
input:
10 9
output:
508778235
result:
ok 1 number(s): "508778235"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3472kb
input:
69 3
output:
11497815
result:
ok 1 number(s): "11497815"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
994 515
output:
33689623
result:
ok 1 number(s): "33689623"
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 3544kb
input:
4476 6182
output:
505051055
result:
wrong answer 1st numbers differ - expected: '114894183', found: '505051055'