QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#41624 | #1084. Beautiful Sequence Unraveling | Antistar | AC ✓ | 1093ms | 7040kb | C++20 | 1.5kb | 2022-07-31 13:43:36 | 2022-07-31 13:43:37 |
Judging History
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);
}
詳細信息
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"