QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#41624#1084. Beautiful Sequence UnravelingAntistarAC ✓1093ms7040kbC++201.5kb2022-07-31 13:43:362022-07-31 13:43:37

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-31 13:43:37]
  • Judged
  • Verdict: AC
  • Time: 1093ms
  • Memory: 7040kb
  • [2022-07-31 13:43:36]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
int mo;
const int N = 405;
int n, K, ipw[N][N], pw[N][N];
int sf[N][N], f[N][N], h[N], binom[N][N];

int main() {
  scanf("%d%d%d", &n, &K, &mo);
  ipw[1][1] = 1;
  for (int i = 2; i <= n; i++)
    ipw[i][1] = mo - 1ll * (mo / i) * ipw[mo % i][1] % mo;
  for (int i = 1; i <= n; i++) {
    ipw[i][0] = pw[i][0] = 1, pw[i][1] = i;
    for (int j = 2; j <= n; j++) {
      ipw[i][j] = 1ll * ipw[i][j - 1] * ipw[i][1] % mo;
      pw[i][j] = 1ll * pw[i][j - 1] * i % mo;
    }
  }
  for (int i = 0; i <= n; i++)
    for (int j = binom[i][0] = 1; j <= i; j++)
      binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % mo;

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      f[i][j] = pw[j][i];
      for (int k = 1; k <= j; k++) {
        f[i][j] = (f[i][j]                                                             //
                   - 1ll * pw[k][i] * (sf[j - k + 1][k] - sf[j - k][k] + mo) % mo + mo //
                   + 1ll * pw[k - 1][i] * (sf[j - k + 1][k - 1] - sf[j - k][k - 1] + mo)) %
                  mo;
      }
    }
    for (int j = 1; j <= n; j++)
      for (int k = 1; k <= n; k++)
        sf[j][k] = (sf[j][k] + 1ll * f[i][j] * ipw[k][i]) % mo;
  }
  int res = 1, ans = 0;
  for (int i = 1; i <= n; i++) {
    res = 1ll * res * (K - i + 1) % mo * ipw[i][1] % mo;
    h[i] = f[n][i];
    for (int j = 1; j < i; j++)
      (h[i] += mo - 1ll * h[j] * binom[i][j] % mo) %= mo;
    ans = (ans + 1ll * h[i] * res) % mo;
  }
  printf("%d\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3704kb

input:

2 2 1000000007

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3 4 1000000009

output:

36

result:

ok 1 number(s): "36"

Test #3:

score: 0
Accepted
time: 202ms
memory: 5596kb

input:

228 112263 998244353

output:

379700769

result:

ok 1 number(s): "379700769"

Test #4:

score: 0
Accepted
time: 2ms
memory: 3864kb

input:

1 1 998595277

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 2ms
memory: 5832kb

input:

2 2 998683811

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 2ms
memory: 5828kb

input:

3 1 998277223

output:

0

result:

ok 1 number(s): "0"

Test #7:

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

input:

4 1 998365733

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 1092ms
memory: 6888kb

input:

400 100000000 998244353

output:

318973800

result:

ok 1 number(s): "318973800"

Test #9:

score: 0
Accepted
time: 1036ms
memory: 6968kb

input:

400 1 1000000007

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 3ms
memory: 5696kb

input:

2 9 999603883

output:

72

result:

ok 1 number(s): "72"

Test #11:

score: 0
Accepted
time: 2ms
memory: 3720kb

input:

1 1 998784541

output:

1

result:

ok 1 number(s): "1"

Test #12:

score: 0
Accepted
time: 3ms
memory: 5836kb

input:

3 3 999209353

output:

12

result:

ok 1 number(s): "12"

Test #13:

score: 0
Accepted
time: 2ms
memory: 5836kb

input:

4 12 999787531

output:

16544

result:

ok 1 number(s): "16544"

Test #14:

score: 0
Accepted
time: 1071ms
memory: 6968kb

input:

400 3 998785127

output:

505031599

result:

ok 1 number(s): "505031599"

Test #15:

score: 0
Accepted
time: 1038ms
memory: 7040kb

input:

400 77 999400643

output:

877578741

result:

ok 1 number(s): "877578741"

Test #16:

score: 0
Accepted
time: 1093ms
memory: 6868kb

input:

400 374 998458939

output:

202865317

result:

ok 1 number(s): "202865317"

Test #17:

score: 0
Accepted
time: 1062ms
memory: 6964kb

input:

400 77435643 999245677

output:

833344996

result:

ok 1 number(s): "833344996"

Test #18:

score: 0
Accepted
time: 1090ms
memory: 6948kb

input:

399 72119824 999010279

output:

188282648

result:

ok 1 number(s): "188282648"

Test #19:

score: 0
Accepted
time: 1054ms
memory: 6924kb

input:

398 22521432 999827603

output:

986913334

result:

ok 1 number(s): "986913334"

Test #20:

score: 0
Accepted
time: 1021ms
memory: 6976kb

input:

397 77955743 998803427

output:

32764673

result:

ok 1 number(s): "32764673"