AtCoder Grand Contest046-B Extension 解説

実質1行のDPなんですが、コンテスト後のTLを観たら結構いろんな解き方がされていて、割と自分の実装は短く済んでいる方だということがわかったので結論だけ簡単に示しておこうと思います。

問題ページ：https://atcoder.jp/contests/agc046/tasks/agc046_b

解法

dp[i][j] := 縦iマス、横jマスの長方形になった時の黒マスの塗り方とします。i < A or j < B ならdp[i][j] = 0です（なぜなら最初から縦Aマス、横Bマスの状態で出発し、サイズが小さくなることはないから）。また、dp[A][B] = 1です。求める答えはdp[C][D]です。

現在、縦(i - 1)、横jの長さの長方形ができているとします。この時、「横」を選んで、縦方向に1拡張する操作を操作Aとしましょう。操作Aの結果新たに塗られる黒いマスの塗り方は、j通りです。同様に、縦i、横(j - 1)の長さの長方形に対して「縦」を選んで横方向に1拡張する時新たに塗られる黒いマスの塗り方はi通りです（この操作を操作Bとします）。

縦i、横jの長方形にたどり着く直前の操作は上述の操作AまたはBのいずれかに限られます。ところで、操作Aで拡張された長さjの辺において、一番右端のマスを黒く塗った場合、それによって得られる長方形の模様は操作Bからは絶対に得られないことがわかります（なぜなら、操作Bを行う前に、縦の長さはiになっており、その時点で、横幅(j-1)の長方形グリッドの一番上の行のどこかは必ず黒マスになっているからです）操作Bで一番上のマスを黒く塗った場合も同様です。

一方で、操作Aで拡張された長さjの辺において、一番右端以外のマスを黒く塗って得られる長方形の模様は、操作Bからも得られます。操作Bも同様です。

これらの考察から、はじめに操作A、操作Bによって得られうる長方形の模様を全部計算しておき、そこから、マス(i , j)を黒く塗らないような塗り方を引くことによって重複を取り除くことができます。実装は次の通りです。

mint dp[3030][3030]; // mint : modint class
void solve(){
  dp[a][b] = 1;
  
  for(int i = a + 1;i <= c ;i++){
    dp[i][b] = dp[i-1][b] * (mint)b;
  }
 
  for(int i = b + 1;i <= d ;i++){
    dp[a][i] = dp[a][i-1] * (mint)a;
  }
 
  for(int i = a + 1;i <= c ;i++){
    for(int j = b + 1;j <= d ;j++){
      dp[i][j] = dp[i][j-1] * (mint)i 
　　　　　　　　　　+ dp[i-1][j] * (mint)j 
　　　　　　　　　　- (mint)((i-1)*(j-1))*dp[i-1][j-1];
    }
  }
  cout << dp[c][d] << '\n';
}

(i-1)*(j-1)*dp[i-1][j-1]は、縦(i-1)、横(j-1）の長方形を縦と横にそれぞれ1ずつ拡張して、拡張された辺に1つずつ黒マスを付ける付け方を数えています。書いておいてなんですが改めて見るとこれで通るのはちょっと不思議な感じがしています。