QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185024 | #2603. Disbalance | yllcm | WA | 16ms | 19440kb | C++14 | 2.2kb | 2023-09-21 16:01:23 | 2023-09-21 16:01:24 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define mp make_pair
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define FR first
#define SE second
using namespace std;
inline int read() {
int x = 0; bool op = false;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 2e6 + 10;
const int P = 998244353;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int ksm(int x, int k) {
int res = 1;
for(int pw = x; k; (k & 1) ? res = 1ll * res * pw % P : 0, pw = 1ll * pw * pw % P, k >>= 1);
return res;
}
int fac[N], ifac[N];
void init() {
fac[0] = ifac[0] = 1;
for(int i = 1; i < N; i++)fac[i] = 1ll * fac[i - 1] * i % P;
ifac[N - 1] = ksm(fac[N - 1], P - 2);
for(int i = N - 2; i; i--)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
return ;
}
int com(int n, int m) {return n < m || m < 0 ? 0 : 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
int ff(int n, int m) {return n < m || m < 0 ? 0 : 1ll * fac[n] * ifac[n - m] % P;}
int calc(int l, int r, int m) {
int res = 0;
add(res, com(r + 1, m + 1));
sub(res, com(l, m + 1));
return res;
}
int n, k;
void solve() {
n = read(); k = read();
int ans = 0;
for(int i = 1; i <= k; i++) {
if(n == 1)add(ans, i + 1);
else {
int res = 0, tl = (n + i + 1) / 2, tr = i + 1;
add(res, 1ll * (i + n + 2) * calc(i + n - tr, i + n - tl, n - 1) % P);
sub(res, 2ll * n * calc(i + n - tr + 1, i + n - tl + 1, n) % P);
// printf("i:%d %d %d %d\n", i, tl, tr, res);
add(ans, 1ll * res * ksm(com(n + i - 1, i), P - 2) % P);
}
}
// for(int i = 1; i <= k; i++) {
// for(int j = 1; j <= i + 1; j++) {
// int v = 1ll * calc(n + i - j, n - 1) * max(0, 2 * j - (n + i)) % P * n % P;
// add(ans, 1ll * v * ksm(com(n + i - 1, i), P - 2) % P);
// }
// }
printf("%lld\n", 1ll * n * ans % P);
return ;
}
int main() {
init();
int test = read();
while(test--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 16ms
memory: 19440kb
input:
8 1 1 1 2 2 1 2 2 3 1 3 2 3 3 4 3
output:
2 5 1 332748120 0 499122177 299473307 598946612
result:
ok 8 numbers
Test #2:
score: -100
Wrong Answer
time: 16ms
memory: 19412kb
input:
20 9 12 2 6 9 14 3 7 1 2 1 2 10 11 6 7 10 13 7 4 1 3 4 4 2 2 1 5 10 9 6 10 7 5 7 4 10 7 4 3
output:
208142452 385037126 276487532 827116758 5 5 161199746 305739342 383431478 0 9 570425345 332748120 20 334869712 195709745 0 0 0 598946612
result:
wrong answer 1st numbers differ - expected: '601023541', found: '208142452'