QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#806271	#4223. 盒	nhuang685^#	20	429ms	3656kb	C++23	2.0kb	2024-12-09 02:01:56	2024-12-09 02:01:57

Judging History

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

[2024-12-09 02:01:57]
评测

测评结果：20
用时：429ms
内存：3656kb

查看

[2024-12-09 02:01:56]
提交

answer

#include "bits/stdc++.h"

constexpr int MOD = 998'244'353;
constexpr int MX = 2000;
struct Mint {
  int val;
  explicit Mint(int v = 0) : val((v % MOD + MOD) % MOD) {}
  Mint& operator+=(const Mint& rhs) {
    val += rhs.val;
    if (val >= MOD) {
      val -= MOD;
    }
    return *this;
  }
  Mint& operator*=(const Mint& rhs) {
    val = static_cast<int>(1LL * val * rhs.val % MOD);
    return *this;
  }
  Mint binpow(int pw) const {
    Mint res{1}, a{*this};
    while (pw > 0) {
      if (pw % 2 == 1) {
        res *= a;
      }
      a *= a;
      pw /= 2;
    }
    return res;
  }
  Mint inv() const { return binpow(MOD - 2); }
};
Mint operator+(Mint lhs, const Mint& rhs) { return lhs += rhs; }
Mint operator*(Mint lhs, const Mint& rhs) { return lhs *= rhs; }
std::vector<Mint> fac, ifac;
Mint comb(int n, int k) {
  if (n < k || n < 0 || k < 0) {
    return Mint{0};
  }
  return fac[n] * ifac[k] * ifac[n - k];
}
Mint sb(int n, int k) {
  return comb(n + k - 1, k - 1);
}

void solve() {
  int n;
  std::cin >> n;

  std::vector<int> a(n);
  for (int& v : a) {
    std::cin >> v;
  }
  std::vector<Mint> w(n - 1);
  for (Mint& v : w) {
    std::cin >> v.val;
  }

  Mint ans{0};
  int s = std::accumulate(a.begin(), a.end(), 0);
  int pre = 0;
  for (int i = 0; i < n - 1; ++i) {
    pre += a[i];
    for (int lhs = 0; lhs <= s; ++lhs) {
      int diff = std::abs(lhs - pre);
      Mint nl = sb(lhs, i + 1);
      Mint nr = sb(s - lhs, n - i - 1);
      ans += nl * nr * w[i] * Mint{diff};
    }
  }
  std::cout << ans.val << '\n';
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);


  fac.resize(MX + 1);
  ifac.resize(MX + 1);
  fac[0] = Mint{1};
  for (int i = 1; i <= MX; ++i) {
    fac[i] = fac[i - 1] * Mint{i};
  }
  ifac[MX] = fac[MX].inv();
  for (int i = MX - 1; i >= 0; --i) {
    ifac[i] = ifac[i + 1] * Mint{i + 1};
  }

  int t;
  std::cin >> t;
  while (t--) {
    solve();
  }
}

源文件, 语言: C++23

详细

Pretests

Final Tests

Test #1:

score: 5

Accepted

time: 1ms

memory: 3544kb

input:

output:

result:

ok 1000 lines

Test #2:

score: 5

Accepted

time: 1ms

memory: 3648kb

input:

output:

result:

ok 1000 lines

Test #3:

score: 5

Accepted

time: 0ms

memory: 3476kb

input:

5
9
2 1 2 1 1 1 0 0 1
64441563 797608723 942502970 533863371 513086090 746473949 428148282 824687114
9
2 1 0 0 1 1 2 1 1
357194979 60738266 185201880 659655681 91157881 186097011 305593400 735854260
9
5 1 0 1 0 1 0 0 1
100945837 161415380 584897137 338229880 478210934 517640875 276897589 404899480
9...

output:

result:

ok 5 lines

Test #4:

score: 5

Accepted

time: 0ms

memory: 3596kb

input:

5
9
2 1 0 3 0 1 2 0 0
14399309 615700834 990195320 232910103 497942608 662410204 85583523 29348873
9
0 4 0 0 0 2 3 0 0
666973109 216575957 709836635 363606637 454780119 714712114 868661423 39323875
9
3 3 0 0 0 0 1 1 1
661125856 61965314 875115448 444871086 310288485 430098658 795362211 948050121
9
2...

output:

result:

ok 5 lines

Test #5:

score: 0

Wrong Answer

time: 424ms

memory: 3532kb

input:

10
2000
0 0 3 0 3 0 0 0 4 0 4 0 0 0 7 3 3 0 0 0 0 1 1 0 2 3 1 3 3 2 1 0 0 0 0 1 0 1 1 0 1 0 4 2 0 0 0 0 0 0 0 1 1 4 1 2 0 0 3 1 5 0 0 0 1 7 2 3 2 0 1 0 5 0 5 0 0 0 4 2 2 0 0 0 2 0 3 1 1 0 0 4 1 2 1 4 2 0 0 1 1 5 0 4 0 1 0 2 1 0 2 0 0 0 1 1 1 0 0 0 0 4 1 2 0 0 0 1 0 4 2 0 2 1 0 0 1 0 0 0 0 0 2 1 1 3 ...

output:

result:

wrong answer 1st lines differ - expected: '677203754', found: '435422782'

Test #6:

score: 0

Wrong Answer

time: 429ms

memory: 3656kb

input:

10
2000
0 1 0 2 0 0 1 0 0 3 1 4 1 1 0 0 2 0 0 0 1 1 6 1 0 0 0 0 0 1 0 0 0 0 0 2 0 0 3 0 0 0 0 0 5 1 0 0 2 1 0 1 2 0 5 0 0 0 0 5 4 4 0 2 3 0 0 3 2 3 0 0 1 2 0 1 9 0 1 0 0 0 3 1 6 1 1 0 2 0 0 0 1 1 4 0 3 3 0 2 1 0 1 0 1 0 0 1 1 0 0 6 0 0 4 0 1 0 4 0 0 0 0 1 0 0 2 4 0 1 0 1 1 7 0 1 0 0 0 3 0 0 2 2 1 1 ...

output:

result:

wrong answer 1st lines differ - expected: '13138131', found: '83854487'

Test #7:

score: 0

Wrong Answer

time: 427ms

memory: 3516kb

input:

10
2000
0 1 0 0 2 2 0 1 1 0 1 0 0 1 2 1 0 0 1 0 0 1 0 2 0 0 0 0 0 1 0 0 0 1 1 1 2 1 0 0 2 0 2 0 0 7 0 0 0 1 3 1 0 1 2 1 0 1 0 2 1 2 2 0 0 0 0 0 0 2 0 1 2 1 0 1 1 0 2 0 3 0 0 1 1 1 0 2 0 0 0 0 1 0 0 0 0 0 0 2 0 1 0 7 0 4 2 0 0 1 0 0 1 0 0 5 0 0 2 3 2 0 1 2 0 1 0 5 0 0 3 3 2 0 1 1 4 0 2 1 0 1 1 1 0 0 ...

output:

result:

wrong answer 1st lines differ - expected: '927739833', found: '209426750'

Test #8:

score: 0

Wrong Answer

time: 427ms

memory: 3616kb

input:

10
2000
0 0 1 0 3 0 0 0 0 2 2 2 1 0 0 2 0 0 0 1 2 1 0 1 0 0 1 1 0 0 2 0 3 1 2 0 1 0 2 1 0 0 0 0 0 2 1 0 1 0 2 1 0 1 2 0 0 0 0 3 1 3 0 0 0 1 2 0 2 0 3 1 0 1 1 0 1 0 1 0 0 0 3 0 0 2 2 1 1 2 6 0 0 0 0 0 1 1 1 0 0 1 2 0 1 1 4 1 0 0 0 0 2 0 1 1 1 1 2 2 1 3 2 0 1 1 0 0 0 0 2 2 0 0 0 0 0 1 2 0 1 1 1 0 2 0 ...

output:

result:

wrong answer 1st lines differ - expected: '195292244', found: '975228659'

Test #9:

score: 0

Runtime Error

input:

10
2000
5 18 179 19 200 71 72 241 70 268 2 32 43 179 39 436 69 57 77 196 212 93 57 128 66 29 248 16 279 102 286 38 12 122 3 84 51 91 39 4 59 31 129 278 3 258 67 171 18 92 80 97 35 48 87 167 22 0 152 110 195 174 59 102 354 136 11 82 87 56 21 78 172 376 79 284 21 51 66 46 97 251 12 92 13 53 31 25 60 9...

output:

result:

Test #10:

score: 0

Runtime Error

input:

10
2000
85 186 177 278 2 12 67 247 6 197 142 32 47 61 13 33 184 9 198 71 82 157 61 129 204 35 67 91 261 104 47 47 149 126 15 45 74 278 250 56 217 13 38 120 67 2 20 74 0 8 75 43 120 83 52 112 41 98 22 5 74 184 33 194 109 73 109 59 103 6 39 146 118 26 1 9 0 93 8 246 56 83 2 43 101 68 36 103 384 130 17...

output:

result:

Test #11:

score: 0

Runtime Error

input:

10
2000
28 10 97 27 85 51 88 20 290 96 147 63 31 171 29 55 325 87 73 70 60 23 1 69 370 389 63 74 206 60 28 74 312 346 26 45 389 137 76 137 377 386 5 246 54 344 11 50 55 418 30 76 205 66 41 112 198 106 29 44 176 6 21 1 20 72 74 2 40 135 47 286 104 63 19 112 4 98 6 56 113 189 57 177 1 70 177 26 153 26...

output:

result:

Test #12:

score: 0

Runtime Error

input:

10
2000
53 99 243 121 0 61 132 124 135 6 191 8 149 19 114 56 93 55 65 35 75 68 2 397 39 117 66 177 203 134 91 67 44 12 94 23 283 176 103 62 273 307 16 126 173 208 54 69 2 15 33 52 82 84 188 178 73 187 39 22 76 27 29 123 18 33 96 66 78 192 9 47 115 60 44 65 203 25 100 54 309 68 71 42 380 121 6 79 295...

output:

result:

Test #13:

score: 0

Runtime Error

input:

2
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

result:

Test #14:

score: 0

Runtime Error

input:

2
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

result:

Test #15:

score: 0

Runtime Error

input:

2
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

result:

Test #16:

score: 0

Runtime Error

input:

2
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

result:

Test #17:

score: 0

Runtime Error

input:

2
200000
0 0 0 0 1 2 0 0 2 0 0 1 2 0 1 0 0 2 0 1 3 0 0 5 4 1 0 1 2 0 3 2 0 3 0 1 0 1 3 0 0 2 0 3 3 0 1 0 0 0 0 0 2 0 0 0 2 1 0 0 2 2 1 3 1 0 0 1 0 0 0 0 1 7 0 0 0 3 0 3 2 0 5 0 6 0 1 0 1 2 2 0 3 2 5 2 1 0 0 0 1 1 3 1 0 0 4 0 0 0 0 0 1 0 1 1 0 0 3 3 1 0 0 4 1 1 0 0 1 0 2 0 0 2 0 1 0 0 0 2 0 4 0 0 2 1...

output:

result:

Test #18:

score: 0

Runtime Error

input:

2
200000
0 2 1 0 0 0 2 0 0 2 2 1 7 3 0 0 3 0 0 4 1 1 0 5 1 1 2 0 0 2 0 2 0 2 0 1 1 2 0 0 1 0 2 3 2 0 0 0 0 2 0 2 0 1 2 0 1 0 4 0 0 2 0 1 0 1 0 0 0 5 0 1 0 0 1 2 1 2 0 2 1 0 0 1 0 0 0 2 0 1 0 1 0 1 0 3 0 2 1 1 1 1 1 1 0 1 0 0 7 2 3 0 0 1 1 1 2 0 0 1 2 0 0 0 2 2 0 0 3 0 0 1 2 0 0 5 1 0 0 0 0 0 3 2 0 0...

output:

result:

Test #19:

score: 0

Runtime Error

input:

5
500000
11 7 4 2 1 24 2 6 2 5 0 1 1 0 7 1 0 16 3 1 0 2 2 0 9 3 1 5 0 0 0 7 1 13 11 4 0 0 2 5 2 2 3 1 1 11 3 0 0 4 1 4 3 1 0 12 2 4 2 3 6 6 1 3 10 1 1 1 10 1 2 1 0 13 6 18 1 1 7 3 2 12 3 1 1 2 6 12 0 1 9 14 7 3 0 0 1 2 1 3 2 8 2 2 5 2 7 0 4 6 7 11 2 7 1 1 0 1 1 9 6 6 5 1 3 8 0 2 0 0 6 3 0 0 2 0 1 5 ...

output:

result:

Test #20:

score: 0

Runtime Error

input:

5
500000
13 6 2 0 3 4 3 1 2 2 14 5 0 5 1 3 2 6 0 5 8 0 15 2 0 2 0 11 2 0 1 0 7 0 11 2 6 3 8 0 3 0 1 2 0 1 3 7 0 9 0 0 2 4 5 0 6 20 4 1 1 3 3 1 2 2 1 0 1 12 9 5 3 0 0 1 4 18 0 8 10 8 7 1 4 23 1 4 1 6 0 6 2 1 4 1 2 0 0 4 19 9 4 4 0 3 1 14 2 6 1 14 0 7 0 1 0 1 2 0 17 0 8 19 1 0 2 3 1 0 6 3 0 2 5 3 0 1 ...