はまやんはまやんはまやん

hamayanhamayan's blog

Union [CODE THANKS FESTIVAL 2018 E]

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;
}