Educational Codeforces Round 49 E. Inverse Coloring

問題リンク
Problem - E - Codeforces

問題概要
n*nの正方形を白か黒のどちらかで塗りつぶすとき, 次の条件を満たすものの組み合せ数を答える
・隣接する行および列は同じ色か異なる色でなければならない. （言い換えると, 白に縦1*横3と塗っている場合, その下の行には白の1*3か黒の1*3しか来ないみたいな感じ）
・塗った時にできる長方形の大きさがk未満

考えたこと

nは高々500なので動的計画法を考える.
長方形で埋めていくような感じでいくつか例を挙げる. すると, 縦と横のブロック幅を決めると, マスの面積が確定することが分かる.

よって, ブロック幅 nの分割の仕方の総数を求める問題に帰着できる.

長方形のサイズがkを超えないようにするため次のようなdpを考える
dp[i][j][k] = nに関してi以下の数字しか使わないとき, 残り数がjでiが含まれている(k=1)場合の組合せの数

あとは, 横と縦の分割の組合せを求めればよく, これは先ほどのdpの情報を使って求めることができる.

自分の実装だと, 横の幅をi=1~nまで全探索して, 縦に関してはmin((k-1)/i, n)にする.

    for(int i=1; i<=n; i++){
      ll t = dp[i][n][1] * dp[min((k-1)/i, n)][n][0];
      t %= mod2;
      ans += t;
      ans %= mod2;
    }

白と黒の2通りがあるので最後に2倍する

実装例
codeforces.com