QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#712759#1839. JokehswfwkjWA 0ms3692kbC++141.3kb2024-11-05 16:56:232024-11-05 16:56:23

Judging History

你现在查看的是最新测评结果

  • [2024-11-05 16:56:23]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3692kb
  • [2024-11-05 16:56:23]
  • 提交

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], cout << "nm";
	}
	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[0][x] % mod * f[j][k] % 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: 3628kb

input:

2
1 2
2 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

4
4 3 2 1
4 3 2 1

output:

16

result:

ok 1 number(s): "16"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3692kb

input:

5
1 2 3 4 5
0 0 0 0 0

output:

nmnmnmnmnm120

result:

wrong output format Expected integer, but "nmnmnmnmnm120" found