QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185024#2603. DisbalanceyllcmWA 16ms19440kbC++142.2kb2023-09-21 16:01:232023-09-21 16:01:24

Judging History

你现在查看的是最新测评结果

  • [2023-09-21 16:01:24]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:19440kb
  • [2023-09-21 16:01:23]
  • 提交

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'