https://kyopro.hateblo.jp/entry/2018/09/23/021755

問題. 半分

非負整数列 $A_1, \ldots, A_n$ と非負整数 $K$ が与えられる．数列にちょうど $K$ 回の操作を行ったあとの数列としてありうるものの個数を求めよ．ただし，各操作とは $1 \le i \le n$ 番目の要素を 2 で割った商の小数点以下切り捨てた値に置き換えることである．

制約： $1 \le n \le 50$ ，　 $0 \le A_i \le 10^{18}$ ，　 $0 \le K \le 10^9$

解法. 動的計画法

解けなかったので解説 [1] を参考にした．

$c(i)$ を， $A_i$ を 0 にするのに行った操作の回数とする．このとき，1回の操作で要素の値は半分となるので，各要素に対して高々60回の操作しか行わない．
操作を行ったあとの数列の個数を動的計画法で求めることを考える． $f(i, j)$ を部分列 $A_1, A_2, \ldots, A_i$ に対してちょうど $j$ 回操作を行った後の数列としてありうるものの個数，として漸化式を考えたいが上手くいかない．なぜならば，要素0に対しても操作が行えて，操作後の数列が変らないので，操作の回数が異なっても同じ数列を数えている場合があるからである．したがって，操作後の数列で0を含むものと含まないものを分けて数えてみることにする．
　 $f_1(i, j) :=$ 部分列 $A_1, \ldots, A_i$ でちょうど $j$ 回操作を行って，要素に0を含まない数列の個数
　 $f_2(i, j) :=$ 〃，少なくとも1つの要素に0を含む数列の個数（ただし，0の要素はこれ以上操作を行わない）
先程とは異なり，このように定義すると操作の回数が異なっていると異なる数列を数えていることになる．また， $f_2$ で0の要素に対して操作を行わないようにしたのも，異なる数列を数えられるようにしたためである．
各 $1 \le i \le n$ と $0 \le j \le \sum_{k=1}^{i} c(i)$ に対して漸化式を考える．ただし， $f_1(0, 0) := 1$ とする．漸化式は，
　 $f_1(i, j) := \sum_{j - c(i) + 1 \le j' \le j} f_1(i - 1, j')$ ，
　 $f_2(i, j) := f_1(i - 1, j - c(i)) + \sum_{j - c(i) \le j' \le j} f_2(i - 1, j')$
となる． $f_2$ の右辺は，0を含まない列と含む列に $A_i$ に操作を行ったものを加えた数列を数えている． $S = \sum_{i=1}^{n} c(i)$ とすると，上の漸化式から $S \le j$ に対しては $f_1(i, j) = f_2(i, j) = 0$ となるので，答えは，
　 $f_1(n, K) + \sum_{i = 0}^{\min(S, K)} f_2(n, i)$
となる．

計算時間： $O(n^2 (\log A)^2)$ 　（ $A$ は数列の要素の最大値）

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    ll n, k;
    cin >> n >> k;

    vector<ll> c(n + 1);
    for (ll i = 1, a; i <= n; ++i) {
        cin >> a;
        while (a) {
            ++c[i];
            a /= 2;
        }
    }

    ll sum = accumulate(c.begin(), c.end(), 0);
    if (sum < k) k = sum;

    vector<vector<ll>> dp1(n + 1, vector<ll>(sum + 1));
    vector<vector<ll>> dp2(n + 1, vector<ll>(sum + 1));
    dp1[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= sum; ++j) {
            for (int l = max(0ll, j - c[i] + 1); l <= j; ++l)
                dp1[i][j] = (dp1[i][j] + dp1[i - 1][l]) % MOD;

            for (int l = max(0ll, j - c[i]); l <= j; ++l)
                dp2[i][j] = (dp2[i][j] + dp2[i - 1][l]) % MOD;
            if (0 <= j - c[i])
                dp2[i][j] = (dp2[i][j] + dp1[i - 1][j - c[i]]) % MOD;
        }
    }

    ll ans = dp1[n][k];
    for (int i = 0; i <= k; ++i)
        ans = (ans + dp2[n][i]) % MOD;

    cout << ans << endl;

    return 0;
}

まとめ

状態をどう定義すればいいのかが分からなかったので残念．
「異なる状態で同じものを数えてしまっている場合は状態を変える」を意識する．

参考文献

[1] Code Festival 予選A 解説（2018年9月23日アクセス）