CODE THANKS FESTIVAL 2018 E - Union (400) - くるのプログラミング記録

リンク：
beta.atcoder.jp
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
問題文
$1 \leq i \leq T$ の範囲の数字 $T$ 個をそれぞれについて $0$ 以上 $a_i$ 以下の好きな個数だけ黒板に書いたあと、次の操作を繰り返す。

・黒板に書かれている整数のうち、 $2$ つ以上ある整数 $X$ を $2$ つ消して、黒板に $X+1$ を1つ書く。

最終的に $1$ つの整数が黒板に書かれているようにできるような整数の書き方は何通りあるかを $mod(10^9 + 7)$ で求めよ。

制約
$1 \leq T \leq 300$
$0 \leq a_i \leq 300$

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

操作を繰り返しても数字を大きくするしか出来ないことが分かる。
よって黒板に書かれた一番小さい数xは1個or偶数個である。

1個のときはそれより大きい数字は書かれていてはいけない。
偶数個のときは愚直に全部の $x$ を $x+1$ に変換すると、一番小さい数が $x+1$ になるため、この数について再び同じように考える。

これを繰り返すと、ある決まった整数の書かれ方について条件を満たしているか判定ができる。
ただし $1 \leq i \leq T$ の各整数の書き方のパターンはおおよそ $a_1 × a_2 ×......× a_T$ なので膨大であり愚直な全探索はできない。

ただこのことから、 $x$ が $2N$ 個あると $x+1$ は $N$ 個増えるということが分かるのでこの遷移を使って $dp$ を書く。

$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}j\end{bmatrix}$ := 整数 $i$ が $j$ 個黒板に書かれているような場合の数。

$i$ の範囲は初期状態の $1$ から $T$ に加えて、整数 $T$ を操作したときのことも考慮して $T+\log_2{T}$ ぐらい必要。

また $j$ の範囲は初期状態の $0$ から $a_i$ に加えて、操作を行い1つ小さい数字の半分の個数が加わることを考慮して $2a_i$ ぐらい必要(雑に漸化式を立てると分かる)

よって $dp$ テーブルを $dp\begin{bmatrix}333\end{bmatrix}\begin{bmatrix}601\end{bmatrix}=0$ とする。

$1 \leq i \leq T$ の各整数は $0 \leq j \leq a_i$ の $j$ 個の範囲で好きに選べるため
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=...=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}a_i\end{bmatrix}=1 (1 \leq i \leq T)$

また各整数 $i$ が $0$ 個のパターンは常に $1$ 通りはあるため
$dp\begin{bmatrix}1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=...=dp\begin{bmatrix}332\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=1$

遷移に関して。
整数 $i-1$ が $2j$ 個あるとき、 $i$ は $j$ 個増えるので、整数 $i$ が $k$ 個のときを考えると $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}k\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}k\end{bmatrix}+dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}k-j\end{bmatrix}×dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2j\end{bmatrix}$

こうして遷移を終えた後の $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$ の和が答えとなる。

以下実装。
遷移の際、更新した値を他の遷移に影響させないために一時的な配列を用いている。
その他は愚直。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;
 
int main() {
  int T; cin >> T;
  vector<ll> a(T+1,0);
  for(int i = 1;i <= T; ++i) {
    cin >> a[i];
  }
  //dpテーブル
  vector<vector<ll>> dp(333, vector<ll>(601, 0));
  
  //各iがa[i]個以下である書き方が1通りずつ
  for(int i = 1; i <= T; ++i) {
    for(int j = 1; j <= a[i]; ++j) {
      dp[i][j] = 1;
    }
  }
  
  //各iが0個である書き方が1通りずつ
  for(int i = 1; i <= 332; ++i) {
    dp[i][0] = 1;
  }
  
  //小さい方から見る
  for(int i = 1; i <= 332; ++i){
    //一時的な配列
    vector<ll> tmp(601, 0);
    
    //遷移
    for(int j = 1; j <= 300; ++j) {
      for (int k = j; k <= 600; ++k) {
        (tmp[k] += (dp[i][k-j]*dp[i - 1][2*j])%MOD)%=MOD;
      }
    }
    
    //更新
    for(int j = 1; j <= 600; ++j) {
      (dp[i][j] += tmp[j]) %= MOD;
    }
  }
  //iが1個になる場合の数を計算
  ll ans = 0;
  for(int i = 1; i <= 332; ++i) {
  	(ans += dp[i][1])%=MOD;
  }
  cout << ans << endl;
  return 0;
}