けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2023-05-04

AtCoder ABC 267 G - Increasing K Time (橙色, 600 点)

AtCoder AtCoder600点 ABC-G 橙色diff DP状態削減テク:全部分集合でなく個数のみ持つ DP 挿入DP 順列の数え上げ数列順列を題材とした問題数え上げ問題制約条件:ちょうどK個探索順序を工夫して解く選択肢が広い方か狭い方から決めていくそのまま覚えたいシンプル設定の中堅以上の典型問題高度典型

順列を数え上げる系の問題、うまく「個数」を持った天才的な DP をするイメージ

問題へのリンク

問題概要

整数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。

この数列の $N!$ 通りの順列のうち、 $A_{i} \lt A_{i+1}$ であるような $i$ がちょうど $K$ 個であるようなものの個数を 998244353 で割ったあまりを求めよ。

制約

$2 \le N \le 5000$
$0 \le K \le N-1$
$1 \le A_{i} \le N$

考えたこと

安直には bitDP をしたくなる。こういう時って、天才的な DP をするイメージ。最初は箱根駅伝 DP かもと思ったけど、なんか違った。

とりあえず、 $A$ を小さい順に並べて、小さい順に挿入していくイメージを考えてみた。そしたらいきなり思いついた！

dp[i][j] ← 数列 $A$ のうち小さい順に $i$ 個を並べる方法のうち、 $A_{k} \lt A_{k+1}$ となっている $k$ の個数がちょうど $j$ 個であるようなものの個数

遷移の詳細を詰めるのは大変だけど、これで $O(N^{2})$ の計算量の解法になった。

コード

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    sort(A.begin(), A.end());
    
    vector<vector<mint>> dp(N+1, vector<mint>(N+1, 0));
    dp[0][0] = 1;
    int m = 0;
    for (int i = 0; i < N; ++i) {
        if (i && A[i-1] < A[i]) m = i;
        for (int j = 0; j <= K; ++j) {
            dp[i+1][j] += dp[i][j] * (i+j+1-m);
            dp[i+1][j+1] += dp[i][j] * (m-j);
        }
    }
    cout << dp[N][K].val() << endl;
}