E - Erasure

問題

$n$ 個のマスが並んでいる．最初全てのマスの色は白である．

これから長さ $k+1$ 以上の区間をいくつか選び，各区間に対して以下の操作を行う．

• 区間を $[l, r]$ とする．
  • $r - l \geq k$
• 各 $l \leq i \leq r$ について，マス $i$ を黒く塗る．

最終的に全てのマスが黒く塗られるような区間の選び方の総数を求めよ．

制約

• $1 \leq k + 1 \leq n \leq 5 \cdot 10^3$

考察

$dp_m =$ 「 $n = m$ のときの答え」を求める． 条件を満たさない選び方を重複なく数えるために，これらを「左から連続する黒マスの数」で区別することにする．

左から黒マスがちょうど $l$ マス連続するような選び方を数える． このとき左から $l+1$ マス目は白，それより右側は自由に塗れる．よって長さ $l$ の区間に含まれる長さ $k+1$ の区間の個数を $p_l$ とすると，そのような選び方は $dp_{l} \cdot 2^{p_{m - l - 1}}$ 通りとなる。

ここで問題文にもある通り， $p_l$ は以下で求まる。

$$ p_l = \begin{cases} 0 & (l \leq k) \\ \frac{(l - k)(l - k + 1)}{2} & (l \gt k) \end{cases} $$

以上より，

$$ \begin{aligned} dp_0 &= 1 \\ dp_m &= 2^{p_m} - \sum_{l = 0}^{m - 1} dp_{l} \cdot 2^{p_{m - l - 1}} \end{aligned} $$

となるので， $p$ を前計算すれば $O(n^2)$ で DP テーブルが埋められる．

実装例

以下では $p_l$ でなく $2^{p_l}$ を前計算している．今回は大丈夫だろうが，累乗は地味に時間が掛かるので注意．

提出 #10080765 - 全国統一プログラミング王決定戦本戦

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <iostream>
#include <vector>

template <int MOD>
struct ModInt { ... };

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;

void solve() {
    int n, k;
    std::cin >> n >> k;

    std::vector<mint> pat(n + 1);
    for (int l = 0; l <= n; ++l) {
        pat[l] = l < k ? 1 : mint(2).pow((l - k) * (l - k + 1) / 2);
    }

    std::vector<mint> just(n + 1, 0);
    just[0] = 1;
    for (int i = 1; i <= n; ++i) {
        just[i] = pat[i];
        for (int l = 0; l < i; ++l) {
            just[i] -= just[l] * pat[i - l - 1];
        }
    }

    std::cout << just[n] << std::endl;
}