ECR154-E Non-Intersecting Subpermutations - zawatinはてなブログ

問題

https://codeforces.com/contest/1861/problem/E (diff 2300)

$1$ 以上 $k$ 以下の整数からなる長さ $n$ の数列 $a$ について、 $a$ の美しさを以下の通り定める。

$a$ から $1$ から $k$ の値が丁度一回ずつ出現する $a$ の連続部分列を、共通区間が存在しないように $p$ 個取り出せるとする
$p$ としてありうる最大値

$1$ 以上 $k$ 以下の整数からなる長さ $n$ の数列 $a$ 全ての美しさの総和 $\mod 998244353$ を求めよ。

制約

$2\ \le\ k\ \lt\ n\ \le\ 4000$

解法

美しさの求め方を考える。尺取り法で $1$ から $k$ の値が丁度一回出現する $a$ の区間を列挙できる。したがって区間スケジューリング問題に帰着する。

今回は全ての区間の長さが $k$ で等しいので、左端がより前のものから貪欲に取るのが正当になる。 (*)

この事実から数え上げを頑張る。

$\text{dp}_{i, j}$ 前から $i$ 項目までを考慮した、「現在区間として取っていない」かつ同じ要素が出現しないsuffixの最大長が $j$ であるような数列の数

とする。(*)から、 $0\ \le\ j\ \le\ k - 1$ のみを考慮すれば良い。なぜなら、同じ要素が出現しないsuffixの最大長が $j\ge k$ 、すなわち $j = k$ のときその区間はすでに取っているからである。

dpの初期値: $\text{dp}_{0, 0} = 1$

dpの遷移

末尾 $j$ 項に登場した値を追加するとき

末尾の値と同じ値を追加すると $\text{dp}_{i + 1, 1}$ に配ることになる

末尾の一個前の値と同じ値を追加すると $\text{dp}_{i + 1, 2}$ に配ることになる

末尾の二個前の値と同じ値を追加すると $\text{dp}_{i + 1, 3}$ に配ることになる

$\vdots$

末尾の $j$ 個前の値と同じ値を追加すると $\text{dp}_{i + 1, j}$ に配ることになる

以上をもらうdpで考え直すと、累積和で高速化できるかたちになる

末尾 $j$ 項に登場しない値を追加するとき

そのような値の候補は $k - j$ 個ある。なので $\text{dp}_{i + 1, j + 1}$ に $(k - j)\times \text{dp}_{i, j}$ を配ることになる。

$j = k - 1$ でかつ最後登場していない値を追加するとき、その区間を「とる」ことになるので、遷移先は $\text{dp}_{i + 1, 0}$

解の計算

dpの計算で区間を取るとき、すなわち「 $j = k - 1$ でかつ最後登場していない値を追加するとき」、残り $n - i - 1$ 項を自由に決めた数列全てがその区間で美しさに寄与するので、 $k^{n - i - 1}\times \text{dp}_{i, k - 1}$ を解に足してあげる

以上より、 $O(nk)$ で本問題を解くことができた。

実装

#include <bits/stdc++.h>

#include "Src/Template/IOSetting.hpp"
using namespace zawa;

#include "atcoder/modint"
using mint = atcoder::modint998244353;

int main() {
    SetFastIO();

    int n, k; std::cin >> n >> k;
    std::vector<mint> dp(k);
    dp[0] = mint::raw(1);
    mint ans{};

    std::vector<mint> P(n + 1);
    P[0] = mint::raw(1);
    for (int i{1} ; i <= n ; i++) P[i] = P[i - 1] * mint{k};

    for (int i{} ; i < n ; i++) {
        std::vector<mint> sum(k + 1);
        for (int j{} ; j < k ; j++) sum[j + 1] += sum[j] + dp[j];
        std::vector<mint> next(k);
        for (int j{} ; j < k ; j++) {
            if (j == k - 1) {
                ans += dp[j] * P[n - i - 1];
                next[0] += dp[j];
            }
            if (j < k - 1) {
                next[j + 1] += mint::raw(k - j) * dp[j];
            }
            // for (int l{1} ; l <= j ; l++) {
            //     next[l] += dp[j];
            // }
        }
        for (int j{1} ; j < k ; j++) {
            next[j] += sum[k] - sum[j];
        }
        dp = std::move(next);
    }
    std::cout << ans.val() << '\n';
}

感想

沢山時間をかけたが、自力で解くことができた。やった。
ARC-CやAGC-A,Bの数え上げ問題を毎回解けずにいるので、今回自力で解けて手応えを感じた。
Fancy Arraysも然り、ECRの数え上げは綺麗な解法が多いと思う