半分 [CODE FESTIVAL 2018 qual A C]

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_c

考察過程

1. Nがあまりに小さいので気になるがbitdpできるような大きさではないので、何か特徴を考える
2. 各要素への操作は独立に行える
3. 2で割る操作は最大60回ぐらいしかできない
4. と考えると、Kは最大3000までしか意味を成さない
5. Kの上限を考えるとDPが作れる

解法

https://beta.atcoder.jp/contests/code-festival-2018-quala/submissions/3243362

DPをする。
dp[i][k][iszero] := i番目まで処理が終わっていて、残りの操作回数がk回であり、今までに0である要素があるかがiszeroである場合の組み合わせ数
　
このままのKで作ると、MLEしてしまう。
2で割る操作は最大60回ぐらいなので、Kは最大3000までしか意味のある操作ができない。
具体的には、3000回を超えると、0の要素を2で割って0にする操作しかできなくなる。
なので、Kは上限にまるめて問題ない。
下のコードでは少し心配だったので、最大10000で丸めている。
　
あとは、iszeroをなぜ含めるかであるが、K回操作を行うが、これはK回丁度操作を行う必要があるためである。
最後までいって操作が余った場合は0の要素に使うことで数列の数を変えることなく消費できる。
なので答えは、dp[N][0][0]とdp[N][0..10000][1]の総和となる。

int N, K; ll A[50];
mint dp[51][10101][2];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    K = min(K, 10000);
 
    dp[0][K][0] = 1;
    rep(i, 0, N) rep(k, 0, 10001) rep(iszero, 0, 2) {
        ll a = A[i];
        int dk = 0;
        int iszero2 = iszero;
        if (a == 0) iszero2 = 1;
 
        dp[i + 1][k][iszero2] += dp[i][k][iszero];
 
        while (0 < a) {
            a /= 2;
            dk++;
 
            if (k - dk < 0) break;
            if (a == 0) iszero2 = 1;
            dp[i + 1][k - dk][iszero2] += dp[i][k][iszero];
        }
    }
    
    mint ans = dp[N][0][0];
    rep(k, 0, 10001) ans += dp[N][k][1];
    cout << ans << endl;
}