QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#41635 | #1084. Beautiful Sequence Unraveling | antiravel | AC ✓ | 970ms | 4916kb | C11 | 1.6kb | 2022-07-31 14:00:29 | 2022-07-31 14:00:30 |
Judging History
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);
}
详细
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"