QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#41635#1084. Beautiful Sequence UnravelingantiravelAC ✓970ms4916kbC111.6kb2022-07-31 14:00:292022-07-31 14:00:30

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 14:00:30]
  • Judged
  • Verdict: AC
  • Time: 970ms
  • Memory: 4916kb
  • [2022-07-31 14:00:29]
  • Submitted

answer

#include <stdint.h>
#include <stdio.h>

#define N 405

int n, m, mod;
int inv_pow[N][N], i_pow[N][N], binom[N][N];
int sf[N][N], f[N][N], h[N];

int main()
{
  scanf("%d%d%d", &n, &m, &mod);
  inv_pow[1][1] = 1;
  for (int i = 2; i <= n; i++)
    inv_pow[i][1] = mod - 1ll * (mod / i) * inv_pow[mod % i][1] % mod;

  for (int i = 1; i <= n; i++)
  {
    inv_pow[i][0] = i_pow[i][0] = 1, i_pow[i][1] = i;
    for (int j = 2; j <= n; j++)
    {
      inv_pow[i][j] = 1ll * inv_pow[i][j - 1] * inv_pow[i][1] % mod;
      i_pow[i][j]   = 1ll * i_pow[i][j - 1] * i % mod;
    }
  }

  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]) % mod;

  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      f[i][j] = i_pow[j][i];
      for (int k = 1; k <= j; k++)
      {
        f[i][j] = (f[i][j] //
                   - (int64_t)i_pow[k][i] * (sf[j - k + 1][k] - sf[j - k][k])
                   + (int64_t)i_pow[k - 1][i]
                         * (sf[j - k + 1][k - 1] - sf[j - k][k - 1]))
                % mod;
      }
    }
    for (int j = 1; j <= n; j++)
      for (int k = 1; k <= n; k++)
        sf[j][k] = (sf[j][k] + (int64_t)f[i][j] * inv_pow[k][i]) % mod;
  }

  int res = 1, ans = 0;
  for (int i = 1; i <= n; i++)
  {
    res  = (int64_t)res * (m - i + 1) % mod * inv_pow[i][1] % mod;
    h[i] = f[n][i];
    for (int j = 1; j < i; j++)
      h[i] = (h[i] - 1ll * h[j] * binom[i][j]) % mod;
    ans = (ans + 1ll * h[i] * res) % mod;
  }

  if (ans < 0)
    ans += mod;

  printf("%d\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 1840kb

input:

2 2 1000000007

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3 4 1000000009

output:

36

result:

ok 1 number(s): "36"

Test #3:

score: 0
Accepted
time: 170ms
memory: 3504kb

input:

228 112263 998244353

output:

379700769

result:

ok 1 number(s): "379700769"

Test #4:

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

input:

1 1 998595277

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 2 998683811

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

3 1 998277223

output:

0

result:

ok 1 number(s): "0"

Test #7:

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

input:

4 1 998365733

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 946ms
memory: 4868kb

input:

400 100000000 998244353

output:

318973800

result:

ok 1 number(s): "318973800"

Test #9:

score: 0
Accepted
time: 940ms
memory: 4872kb

input:

400 1 1000000007

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

2 9 999603883

output:

72

result:

ok 1 number(s): "72"

Test #11:

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

input:

1 1 998784541

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

3 3 999209353

output:

12

result:

ok 1 number(s): "12"

Test #13:

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

input:

4 12 999787531

output:

16544

result:

ok 1 number(s): "16544"

Test #14:

score: 0
Accepted
time: 964ms
memory: 4820kb

input:

400 3 998785127

output:

505031599

result:

ok 1 number(s): "505031599"

Test #15:

score: 0
Accepted
time: 951ms
memory: 4860kb

input:

400 77 999400643

output:

877578741

result:

ok 1 number(s): "877578741"

Test #16:

score: 0
Accepted
time: 970ms
memory: 4916kb

input:

400 374 998458939

output:

202865317

result:

ok 1 number(s): "202865317"

Test #17:

score: 0
Accepted
time: 953ms
memory: 4832kb

input:

400 77435643 999245677

output:

833344996

result:

ok 1 number(s): "833344996"

Test #18:

score: 0
Accepted
time: 938ms
memory: 4912kb

input:

399 72119824 999010279

output:

188282648

result:

ok 1 number(s): "188282648"

Test #19:

score: 0
Accepted
time: 918ms
memory: 4860kb

input:

398 22521432 999827603

output:

986913334

result:

ok 1 number(s): "986913334"

Test #20:

score: 0
Accepted
time: 939ms
memory: 4836kb

input:

397 77955743 998803427

output:

32764673

result:

ok 1 number(s): "32764673"