这种简单题怎么你谷评了紫 /qd

容易发现这个数数和原数组顺序无关，首先对原数组排序，从小往大插入数。

我们记

f_{i,j}

表示插入了前

i

个数，有

k

个位置满足小于的关系。然后考虑转移。我们后面插入一个数，注意到要么使得满足小于的位置数不变，要么加一。我们记

c

表示前

i

个数中等于第

i

个数的数的个数，有转移：

$f_{i-1,j}\times(j+c)\rightarrow f_{i,j}$ ，因为把当前这个数填在这 $j$ 个满足小于的位置之后能发现满足的位置个数仍然不变，或者把当前数填在和他相同的 $c-1$ 个数之后，或者序列开头，也不变，一共 $(j+c)$ 中填法。
$f_{i-1,j}\times(i-j-c)\rightarrow f_{i,j+1}$ ，除去上一种情况的位置都会使得合法位置加一。

初始值

f_{1,0}=1

，最后答案就是

f_{n,k}

。于是做完了。代码很简单。

锐评一下你谷评级，紫也是神人了，感觉只有蓝啊，都能被我做出来。

CPP

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL MOD = 998244353;
const int N = 5e3 + 10;
int n, K, A[N]; LL DP[N][N];

int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> K;
	for (int i = 1; i <= n; i ++) cin >> A[i];
	sort(A + 1, A + 1 + n); DP[1][0] = 1;
	for (int i = 1, c = 1; i < n; i ++) {
		if (A[i] != A[i + 1]) c = 1;
		else ++ c;
		for (int j = 0; j < i; j ++) {
			(DP[i + 1][j] += DP[i][j] * (c + j) % MOD) %= MOD;
			(DP[i + 1][j + 1] += DP[i][j] * (i + 1 - c - j) % MOD) %= MOD;
		}
	} cout << DP[n][K] << "\n";
	return 0;
}

这种简单题怎么你谷评了紫 /qd

文章操作

相关推荐

评论

这种简单题怎么你谷评了紫 /qd