Submission #34443790

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;

using Fp = atcoder::modint998244353;

int main() {
    int N, K;
    cin >> N >> K;
    K += 1;
    vector<int> count(N + 1);
    for (int i = 0; i < N; ++i) {
        int x;
        cin >> x;
        count[x] += 1;
    }
    vector dp(K + 1, Fp(0));
    dp[0] = 1;
    int put = 0, same = 0;
    for (int n = 0; n < N; ++n) {
        while (count[put] == 0) {
            put += 1;
            same = 0;
        }
        vector next(K + 1, Fp(0));
        for (int m = 0; m <= K; ++m) {
            const Fp val = dp[m];
            next[m] += val * (same + m);
            if (m < K) {
                next[m + 1] += val * (n + 1 - m - same);
            }
        }
        dp = move(next);
        count[put] -= 1;
        same += 1;
    }
    cout << dp[K].val() << '\n';
    return 0;
}

Submission Info

Judge Result