QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246157#7632. Balanced Arraysalpha1022AC ✓41ms19568kbC++141.1kb2023-11-10 16:40:342023-11-10 16:40:34

Judging History

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

  • [2023-11-10 16:40:34]
  • 评测
  • 测评结果:AC
  • 用时:41ms
  • 内存:19568kb
  • [2023-11-10 16:40:34]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int mod = 998244353;

void add(int &x, int y) { if ((x += y - mod) < 0) x += mod; }
int quo2(int x) { return (x + (x & 1 ? mod : 0)) >> 1; }

const int N = 5e5;

int n, m;
int inv[N * 2 + 5];
int f[N + 5], fs[N + 5], g[N * 2 + 5], h[N * 2 + 5];
void solve(int n, int w) {
  h[0] = 1, h[1] = n * 2 + 1;
  for (int i = 2; i <= m * 2; ++i)
    h[i] = ((ll)(n * 2 + 1) * h[i - 1] + (ll)(i - 1) * h[i - 2]) % mod * inv[i] % mod;
  for (int i = 0; i <= m * 2; ++i) g[i] = (g[i] + (ll)h[i] * w) % mod;
}

int ans;

int main() {
  scanf("%d%d", &n, &m), ++m;
  inv[1] = 1;
  for (int i = 2; i <= m * 2; ++i) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
  f[0] = 1;
  for (int i = 1; i <= m; ++i)
    f[i] = (ll)(i + quo2(mod - 3)) * f[i - 1] % mod * inv[i] % mod;
  fs[0] = 1;
  for (int i = 1; i <= m; ++i) add(fs[i] = f[i], fs[i - 1]);
  solve(n - 1, 1), solve(n, mod - 2), solve(n + 1, 1);
  for (int i = 0; i <= m; ++i)
    ans = (ans + (ll)g[i * 2] * f[i] % mod * fs[m - i]) % mod;
  if (ans = quo2(ans)) ans = mod - ans;
  printf("%d\n", ans);
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 10012kb

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 33ms
memory: 19416kb

input:

500000 500000

output:

984531374

result:

ok 1 number(s): "984531374"

Test #3:

score: 0
Accepted
time: 0ms
memory: 10008kb

input:

500000 1

output:

219705876

result:

ok 1 number(s): "219705876"

Test #4:

score: 0
Accepted
time: 33ms
memory: 19540kb

input:

1 500000

output:

500001

result:

ok 1 number(s): "500001"

Test #5:

score: 0
Accepted
time: 25ms
memory: 17008kb

input:

500000 353535

output:

33730077

result:

ok 1 number(s): "33730077"

Test #6:

score: 0
Accepted
time: 37ms
memory: 19568kb

input:

353535 500000

output:

182445298

result:

ok 1 number(s): "182445298"

Test #7:

score: 0
Accepted
time: 38ms
memory: 19500kb

input:

499999 499999

output:

933220940

result:

ok 1 number(s): "933220940"

Test #8:

score: 0
Accepted
time: 34ms
memory: 19484kb

input:

499999 499998

output:

899786345

result:

ok 1 number(s): "899786345"

Test #9:

score: 0
Accepted
time: 25ms
memory: 18636kb

input:

377773 400009

output:

206748715

result:

ok 1 number(s): "206748715"

Test #10:

score: 0
Accepted
time: 5ms
memory: 14944kb

input:

499999 100001

output:

482775773

result:

ok 1 number(s): "482775773"

Test #11:

score: 0
Accepted
time: 40ms
memory: 19344kb

input:

444445 488884

output:

70939759

result:

ok 1 number(s): "70939759"

Test #12:

score: 0
Accepted
time: 29ms
memory: 19020kb

input:

488885 444449

output:

591315327

result:

ok 1 number(s): "591315327"

Test #13:

score: 0
Accepted
time: 1ms
memory: 9952kb

input:

500000 111

output:

313439156

result:

ok 1 number(s): "313439156"

Test #14:

score: 0
Accepted
time: 37ms
memory: 18516kb

input:

333333 444444

output:

403492103

result:

ok 1 number(s): "403492103"

Test #15:

score: 0
Accepted
time: 29ms
memory: 17704kb

input:

499994 343433

output:

334451699

result:

ok 1 number(s): "334451699"

Test #16:

score: 0
Accepted
time: 27ms
memory: 19256kb

input:

477774 411113

output:

63883341

result:

ok 1 number(s): "63883341"

Test #17:

score: 0
Accepted
time: 36ms
memory: 18968kb

input:

123456 432109

output:

238795570

result:

ok 1 number(s): "238795570"

Test #18:

score: 0
Accepted
time: 34ms
memory: 19280kb

input:

131331 467777

output:

834790039

result:

ok 1 number(s): "834790039"

Test #19:

score: 0
Accepted
time: 1ms
memory: 9940kb

input:

500000 2

output:

304727284

result:

ok 1 number(s): "304727284"

Test #20:

score: 0
Accepted
time: 1ms
memory: 10004kb

input:

1111 111

output:

98321603

result:

ok 1 number(s): "98321603"

Test #21:

score: 0
Accepted
time: 41ms
memory: 19328kb

input:

416084 493105

output:

916827025

result:

ok 1 number(s): "916827025"

Test #22:

score: 0
Accepted
time: 9ms
memory: 14032kb

input:

53888 138663

output:

57263952

result:

ok 1 number(s): "57263952"

Test #23:

score: 0
Accepted
time: 27ms
memory: 18496kb

input:

219161 382743

output:

304889787

result:

ok 1 number(s): "304889787"

Test #24:

score: 0
Accepted
time: 27ms
memory: 17516kb

input:

181392 318090

output:

12528742

result:

ok 1 number(s): "12528742"

Test #25:

score: 0
Accepted
time: 31ms
memory: 19100kb

input:

135930 422947

output:

554153000

result:

ok 1 number(s): "554153000"

Test #26:

score: 0
Accepted
time: 18ms
memory: 16024kb

input:

280507 210276

output:

812816587

result:

ok 1 number(s): "812816587"

Test #27:

score: 0
Accepted
time: 35ms
memory: 19256kb

input:

253119 420465

output:

124024302

result:

ok 1 number(s): "124024302"

Test #28:

score: 0
Accepted
time: 9ms
memory: 13312kb

input:

446636 97448

output:

150388382

result:

ok 1 number(s): "150388382"

Test #29:

score: 0
Accepted
time: 11ms
memory: 13920kb

input:

284890 126665

output:

786559507

result:

ok 1 number(s): "786559507"

Test #30:

score: 0
Accepted
time: 0ms
memory: 10452kb

input:

186708 28279

output:

607509026

result:

ok 1 number(s): "607509026"

Extra Test:

score: 0
Extra Test Passed