QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#712820 | #1839. Joke | hswfwkj | WA | 0ms | 3708kb | C++14 | 1.3kb | 2024-11-05 17:10:41 | 2024-11-05 17:10:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 103, mod = 998244353;
int n, m, num;
int per[N], p[N];
int pos[N], a[N];
int f[N][N];
int fac[N], sm[N];
int C[N][N];
int used[N], pre[N];
int main()
{
cin >> n;
fac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = 1ll * fac[i - 1] * i % mod;
for (int i = 1; i <= n; ++i)
cin >> per[i];
for (int i = 1; i <= n; ++i)
cin >> p[per[i]];
for (int i = 1; i <= n; ++i)
if (p[i])
pos[++m] = i, used[a[m] = p[i]] = 1;
for (int i = 1; i <= n; ++i)
{
pre[i] = pre[i - 1];
if (!used[i])
++pre[i];
}
pos[++m] = n + 1;
a[m] = n + 1;
f[0][0] = 1;
for (int i = 0; i <= n; ++i)
{
C[i][0] = 1;
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
for (int i = 1; i <= m; ++i)
for (int j = 0; j < i; ++j)
if (a[j] < a[i])
{
for (int k = 0; k <= sm[j]; ++k)
{
int dis = pos[i] - pos[j] - (i - j);
int vdis = pre[a[i] - 1] - pre[a[j]];
int lm = min(dis, vdis);
sm[i] = max(sm[i], sm[j] + lm);
for (int x = 0; x <= lm; ++x)
f[i][k + x] = (f[i][k + x] + 1ll * C[dis][x] * C[vdis][x] % mod * f[j][k] % mod) % mod;
}
}
int res = 0;
for (int i = 0; i <= pre[n]; ++i)
res = res + 1ll * f[m][i] * fac[pre[n] - i] % mod;
cout << res << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
2 1 2 2 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 4 3 2 1 4 3 2 1
output:
16
result:
ok 1 number(s): "16"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
5 1 2 3 4 5 0 0 0 0 0
output:
1546
result:
ok 1 number(s): "1546"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
6 1 6 2 5 3 4 0 1 0 2 0 3
output:
52
result:
ok 1 number(s): "52"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
10 8 2 10 3 4 6 1 7 9 5 0 0 0 0 0 0 0 0 0 0
output:
234662231
result:
ok 1 number(s): "234662231"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
10 5 8 4 9 6 1 2 7 3 10 8 3 0 5 0 9 0 0 6 0
output:
5294
result:
ok 1 number(s): "5294"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
10 4 2 6 9 5 3 8 1 10 7 0 9 8 0 7 3 4 2 1 10
output:
166
result:
ok 1 number(s): "166"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
10 8 2 7 1 5 9 3 4 10 6 7 0 2 9 5 1 8 4 3 6
output:
26
result:
ok 1 number(s): "26"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
10 10 1 6 7 9 8 4 3 5 2 2 5 1 3 9 10 4 8 6 7
output:
47
result:
ok 1 number(s): "47"
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3680kb
input:
50 41 15 17 1 5 31 7 38 30 39 43 35 2 26 20 42 48 25 19 32 50 4 8 10 44 12 9 18 13 36 28 6 27 23 40 24 3 14 29 11 49 47 45 46 34 21 37 16 22 33 0 0 0 0 0 0 0 0 0 33 34 0 0 0 0 0 0 0 0 0 0 2 0 0 0 20 0 0 28 0 0 0 9 0 0 0 48 0 0 0 50 0 0 0 0 5 0 0 32 0
output:
-1532004528
result:
wrong answer 1st numbers differ - expected: '976189245', found: '-1532004528'