概要
正方形のグリッドからなる長方形の盤面がある。各グリッドには、高々一つのブロックを置くことができるが、配置完了後の盤面を正面及び横から見たときの見え方が指定されている。すなわち、ブロックの置かれ方は次の制約を満たす。
- front[ i ] が 'B' であれば、i 列目には一つ以上のブロックが置かれている
- side[ i ] が 'B' であれば、i 行目には一つ以上のブロックが置かれている
制約を満たすブロックの配置は何通りあるか、MOD で求めよ。
解法
まず、front または side のいずれかで '.' であるようなセルにブロックが置かれることはありません。逆に言えば、front, side 共に 'B' であるようなセルにはブロックが置かれる可能性があります。そのようなセルについてだけ考慮すれば十分なので、( side の 'B' の数 ) × ( front の 'B' の数 ) の盤面として考えるとすっきりします。
さて、解法についてですが、いかにも DP なので、どのように状態をとると上手く行くか考えていきます。行の制約と列の制約を同時に満たさなければならないので、それぞれの制約の達成度をパラメータとしてもたなければなりません。が、一行毎に置き方を決めていくようにすると、列に関する制約だけ保持すれば良くなります。ただし、それぞれの列について制約を満たしたかどうかを保持しようとすると最大 になってダメダメなので、もう一工夫必要になります。
ここで着目するのは、一つ以上置かれた列を互いに区別する必要が無い、という点です。そのような列の数が n だとします。このとき、それらの列に対するブロックの置き方は 通りです。
一つも置かれていない列についても同様のことが言えます。その実際の位置を区別せず、数だけに着目して扱うことができます。今、制約を満たした列の数に着目しているので、そのような列が同じ数増える遷移をまとめて扱います。制約を満たしていない列が m 本あり、そこに r 個のブロックを置くとします（制約を満たした列が r 本増える）。このとき、置き方の総数は 通りになります。
状態と遷移がそれなりに少なくできたので、次のような DP が可能であることが分かります。
- dp[ i 行考慮した ][ 一つ以上置かれた列の数が j ] := 置き方の総数
状態遷移は二次元目をいくつ増やすかをそれぞれ試して、dp[ i + 1 ][ j + k ] を更新することになります。更新する値は、現在の状態の値に対し、制約を満たした列・満たしていない列それぞれへの置き方の総数の積を乗じた値です。ただし、k = 0 のとき、制約を満たした列に一つ以上置かないと行の制約を満たさなくなるので、 通りになります。
計算が終わった後、dp[ H ][ W ] の値が答えです。
コード
typedef long long LL; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() const int MOD = 1000000007; // 繰り返し二乗法 x^n を mod で求める long long mod_pow( long long x, long long n, long long mod ); // p が素数のとき、mod p での逆元を求める // フェルマーの小定理 // incluide : mod_pow int mod_inverse( long long a, long long p ); // 素数である mod の剰余系に於ける n! を求める class modFact; // modfact( max_n, mod ) // operator()( n ) // operator()( n, e ) // nCr // include : modFact, mod_inverse class modConb; // modConb( n, mod ) // operator()( n, r ) class BlackBoxDiv2 { public: int count( string front, string side ) { const int H = std::count( ALL( side ), 'B' ); const int W = std::count( ALL( front ), 'B' ); modConb mod_conb( W, MOD ); vector< vector<LL> > dp( H + 1, vector<LL>( W + 1 ) ); dp[0][0] = 1; // dp[ i 行考慮 ][ 一つ以上置いた列が j 列 ] := 場合の数 REP( i, 0, H ) { REP( j, 0, W + 1 ) { REP( k, 0, W - j + 1 ) { LL v1 = mod_pow( 2, j, MOD ); LL v2 = mod_conb( W - j, k ); if ( !k ) { v1 = ( v1 - 1 + MOD ) % MOD; } ( dp[ i + 1 ][ j + k ] += dp[i][j] * v1 % MOD * v2 % MOD ) %= MOD; } } } return dp[H][W]; } };
