Typical DP Contest O - 文字列

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_string

解法

dp[i][j] := i 番目の文字まで見た時，同じ文字が連続している場所が j 箇所あるような場合の数
とする．
例えば，AABBBCDEE なら，連続している箇所は4箇所と数える．

次に追加する文字が f[i] 文字であるとする．
この f[i] 文字を今できている文字列に挿入するときは，f[i] 文字がいくつかのグループに分かれることになる．
そのグループの数を k とし，それぞれのグループを区別すると，その分割の仕方は$_{f[i] - 1}C_{k - 1}$ 通りである．（f[i] - 1箇所から k-1 箇所選んで仕切りを入れると k 個のグループに分かれる．）

次に，こうして分割した各グループをどこに挿入するかを考える．
（さっきのグループを前から 1, ..., k とナンバリングして，選んだ挿入箇所にこの順番で挿入する．）
同じ文字が連続している部分が j 箇所あるので，そのうちの l 箇所にグループを挿入するとする．この場所の選び方は$_jC_l$通りである．
すると，連続していなかった場所に挿入するのは，$_{sum[i] - l + 1}C_{k-l}$通りある．sum[i] はすでにできている文字列の長さで，1 を加えているのは（左）端に挿入する分を考慮している．

最後に，最終的にできた文字列で連続した部分は何通りあるかを考えると，これは j - l + f[i] - k 通りである．（もともと j 箇所あって，l 箇所に挿入されるが，文字 i のグループによって f[i] - k 箇所新たに連続する部分ができる．）

ソースコード

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

using ll = long long;
constexpr ll M = 1e9 + 7;

int main() {
    vector<vector<ll>> comb(512, vector<ll>(512));
    for(int i = 0; i < 512; ++i) {
        for(int j = 0; j <= i; ++j) {
            if(i == j || j == 0) {
                comb[i][j] = 1;
            } else {
                comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % M;
            }
        }
    }

    vector<int> x;
    vector<int> sum = {0};
    for(int i = 0; i < 26; ++i) {
        int f;
        cin >> f;
        if(f == 0) {
            continue;
        }
        x.push_back(f);
        sum.push_back(f + sum.back());
    }

    int const n = x.size();

    vector<vector<ll>> dp(n + 1, vector<ll>(300));
    dp[0][0] = 1;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j <= sum[i]; ++j) {
            for(int k = 1; k <= x[i]; ++k) {
                for(int l = 0; l <= min(j, k); ++l) {
                    ll t = comb[x[i] - 1][k - 1];
                    t = (t * comb[j][l]) % M;
                    t = (t * comb[sum[i] - j + 1][k - l]) % M;
                    t = (t * dp[i][j]) % M;
                    (dp[i + 1][j - l + x[i] - k] += t) %= M;
                }
            }
        }
    }
    cout << dp[n][0] << endl;
}

感想

これは思いつかないなあ．覚えてしまいたい．