https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_e
前提知識
解説
https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664663
DPをする。
dp[i][j] := 整数iまで書かれていて、整数iの個数がjである組み合わせ
下の解法では見積もりをサボってmapでDPを書いている。
dp[i][j]からの遷移は、整数iは全てなくす必要があるので、整数i+1はj/2個できる。
それに加えて、黒板にもともと整数i+1が書かれている可能性がある。
もともと整数i+1がd個書かれているなら、dp[i+1][j/2+d]にdp[i][j]を足すことになる。
足すときにj/2+dは偶数である必要がある。
そうでないと、整数i+1を全て消して整数i+2を作れないためである。
例外として、j/2+d=1のときは、ただ1つの数にできたので、整数i+2以降は全て書かれていない場合として答えに足す。
最後に整数Tが2個以上残った場合は、2の累乗であれば、整数をT+1, T+2のように変化させて1つにできるので、
その場合を答えに足す。
int T, A[303]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> T; rep(i, 0, T) cin >> A[i]; map<int, mint> dp; dp[0] = 1; mint ans = 0; rep(t, 0, T) { map<int, mint> pd; fore(p, dp) { int nxt = p.first / 2; rep(d, 0, A[t] + 1) { if (nxt + d == 1) ans += p.second; if ((nxt + d) % 2 == 0) pd[nxt + d] += p.second; } } swap(dp, pd); } fore(p, dp) if (__builtin_popcount(p.first) == 1) ans += p.second; cout << ans << endl; }