Typical DP Contest - O 文字列

O: 文字列 - Typical DP Contest | AtCoder

• 「同じ文字が隣り合わない」というのを同じ文字がとなりあう部分に別の文字を挿入していくことで表現している。

const int MOD = (int)(1e+9)+7;
static vector<vector<ll>> nCr_impl;
void nCr_init(int maxN) {
        nCr_impl.resize(maxN+1, vector<ll>(maxN+1, 0));
        REP(n, maxN)
        {
            nCr_impl[n][0] = 1;
            REP(r, n+1)
                nCr_impl[n+1][r+1] = (nCr_impl[n][r+1]+nCr_impl[n][r])%MOD;
        }
}
ll nCr(int n, int r) { return nCr_impl[n][r]; }

class o_string {
public:
    void solve(void) {
            vector<int> freq;
            REP(i, 26)
            {
                int f;
                cin>>f;
                // freq = 0 のものは消しておく
                if (f > 0)
                    freq.push_back(f);
            }

            nCr_init(26*10);
            //
            // dp[i][j] := i 番目までの文字を使ったときに同じ文字が
            //             隣り合っている場所が j 個になるような並べ方の総数
            //
            // とする。
            // i+1 番目での (i,j) からの遷移は
            //
            // 1. i+1 番目の文字 X を freq[i] 個を k 個のグループに分割する
            //    このとき freq[i]-k 個の X の右側に X が置かれることになる。
            //
            // XXXXX -> XXX X X
            //       -> XX XX X
            //             :
            //   * k 個のグループの分割方法は  freq[i]-1 C k-1 通り
            //
            // 2. j 個のうち l 個を選んでそこに(その文字の右側に)分割した X を挿入する
            //
            //    AAABBBCCDAB...
            //    ^^ ^  ^
            //   * 挿入点の選び方は j C l 通り
            //
            // 3. 残り k-l 個を連続していない部分に挿入する
            //   * 挿入点の選び方は (len+1-j) C (k-l)      (+1 は左端に挿入するケースを踏まえている)
            //
            // と操作することで決まる。このとき i+1 での隣り合っている場所の個数は
            //   j-l + (freq[i]-k)
            // となる
            //
            int N = freq.size();
            int M = 26*10;
            vector<vector<ll>> dp(N+1,vector<ll>(M+1, 0));
            vector<int>        len(N+1,0);
            REP(i, N)
                len[i+1] = len[i]+freq[i];

            dp[0][0] = 1;
            REP(i, N)
            for (int j = 0; j <= len[i]; ++j)
            for (int k = 1; k <= freq[i]; ++k)
            for (int l = 0; l <= min(j,k); ++l)
            {
                ll tmp = dp[i][j];
                (tmp *= nCr(freq[i]-1,k-1)) %= MOD;
                (tmp *= nCr(j,l)) %= MOD;
                (tmp *= nCr(len[i]+1-j,k-l)) %= MOD;
                (dp[i+1][(j-l)+(freq[i]-k)] += tmp) %= MOD;
            }
            cout<<dp[N][0]<<endl;
    }
};