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

冷却心 · 2025-03-15 22:50:48 · 题解

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

我们记 f_{i,j} 表示插入了前 i 个数，有 k 个位置满足小于的关系。然后考虑转移。我们后面插入一个数，注意到要么使得满足小于的位置数不变，要么加一。我们记 c 表示前 i 个数中等于第 i 个数的数的个数，有转移：

初始值 f_{1,0}=1，最后答案就是 f_{n,k}。于是做完了。代码很简单。

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

#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;
}