問題概要
';' + 1 つ以上の '_' + ';' という文字列を顔文字であるとする．例えば ";_;" や ";____;" は顔文字であるが，";;" や ";_" は顔文字ではない．
';' と '_' からなる文字列 $\mathit{ message }$ が与えられる．$\mathit{ message }$ を重複しない複数の部分列に分けたとき，部分列全てが顔文字となっていて，かつ全ての文字が丁度 1 つの部分列に属するような分け方は何通りあるか？
総数を $X$ として$X \bmod{ 10^9 + 7 }$ を求めよ．
- $1 \leq \mathit{ message } \leq 200$
解法
$| \mathit{ message }| = L$ とします．また，顔文字の左側の ';' を始点，右側の ';' を終点と呼ぶことにします．
構成中の顔文字を持ちながら，手前の文字から順に振り分けていくと考えます．すなわち，各文字に対して
- ';' を新たな顔文字の始点とする
- ';' を手持ちの顔文字のどれかの終点とする（以降この顔文字には '_' を追加できない）
- '_' を手持ちの顔文字のどれかに追加する
という選択肢があると考えます．';' の方は，始点を作る操作は常に可能で，手持ちの顔文字の終点にする操作は，1 回以上 '_' を追加された顔文字にだけ可能です．他方 '_' は，手持ちの閉じられていない顔文字に対して常に操作可能です．このような振り分け方をした後で，手持ちに閉じられていない顔文字が残っていなければ妥当な分割であると言えます．
文字の振り分け方を全通り試していては TLE するので効率的に計算する必要があります．先程の選択肢をよく見ると，「手持ちの顔文字のどれか」を考えるときにそれぞれの個数が必要になりますが，それまでの手順などは関係無いことが分かります．また，手持ちの顔文字が同じなら，それ以降にできることも同じになります．従って，
- dp[ 考慮した文字数 ][ 閉じられない顔文字 (";") の個数 ][ 閉じられる顔文字 (";_...") の個数 ] := この状態に至る手順の総数
という動的計画法を考えることができます．
dp[ i ][ j ][ k ] からの遷移は $\mathit{ message }_i$ によって異なり，
- ';' のとき
- dp[ i + 1 ][ j + 1 ][ k ] += dp[ i ][ j ][ k ] で更新（新たな顔文字の始点とする）
- dp[ i + 1 ][ j ][ k - 1 ] += dp[ i ][ j ][ k ] * k で更新（閉じられる顔文字を閉じる．個数分の選択肢がある）
- '_' のとき
- dp[ i + 1 ][ j ][ k ] += dp[ i ][ j ][ k ] * k で更新（閉じられる顔文字に更に追加する．個数分の選択肢がある）
- dp[ i + 1 ][ j - 1 ][ k + 1 ] += dp[ i ][ j ][ k ] * j で更新（閉じられない顔文字に追加し，閉じられるようにする．個数分の選択肢がある）
となります．
計算が終わったあと，dp[ L ][ 0 ][ 0 ] に答えが求まっています．
この DP の状態数は $O( L^3 )$ 個であり，各状態からの遷移は定数時間で計算できるので，全体で $O( L^3 )$ 時間となります．
コード
using LL = long long; #define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ ) #define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t ) #define SZ( v ) ( (int)( v ).size() ) constexpr int MOD = 1000000007; LL dp[ 256 ][ 256 ][ 256 ]; class BearCries { public: int count( string message ) { { // init for localtest fill( AALL( dp, LL ), 0 ); } const int L = SZ( message ); dp[0][0][0] = 1; // dp[ 考慮文字数 ][ 開いている顔文字の数 ][ 閉じてよい顔文字の数 ] := 場合の数 REP( i, L ) { REP( j, L ) { REP( k, L ) { if ( message[i] == ';' ) { ( dp[ i + 1 ][ j + 1 ][k] += dp[i][j][k] ) %= MOD; if ( k ) { ( dp[ i + 1 ][j][ k - 1 ] += dp[i][j][k] * k ) %= MOD; } } else { // '_' ( dp[ i + 1 ][j][k] += dp[i][j][k] * k ) %= MOD; if ( j ) { ( dp[ i + 1 ][ j - 1 ][ k + 1 ] += dp[i][j][k] * j ) %= MOD; } } } } } return dp[L][0][0]; } };
