Code Festival 2018 予選A C - 半分

問題

長さnの数列aが与えられる
この数列に「好きな要素を1個選んで2で割る(あまりは切り捨てる)」という操作をk回行う
k回の操作の後の数列としてありうるものの個数を求めよ

1 <= n <= 50
0 <= a[i] <= 10^18
0 <= k <= 10^9

解法

最後に出来る数列は各要素に操作を行った回数だけで決まる
また途中で0になった要素はその後何度操作を行っても0のまま変わらない

まず b[i] = (a[i]を何回2で割ると0になるか) という配列bを作る
この値はa[i] <= 10^18 < 2^60だからたかだか60
つまり操作を行うことで数列が変わるような操作はたかだかΣb[i] ≒ 3000回くらいしかできない

dp[i][j][L]: a[i]まででj回操作を行った結果できる数列の個数 (L:0になった要素が存在するかどうか)
このテーブルを埋めれば、求める答えは
dp[n][k][0] + Σdp[n][i][1] (i<=k)
となる
(0になった要素にk-i回操作を行って余りを解消する感じ)

int n, a[55], b[55], k, res, dp[55][3333][2];

signed main() {
	cin >> n >> k;
	rep(i,n) cin >> a[i];
	rep(i,n) {
		int t = a[i];
		while (t) t /= 2, b[i]++;
	}
	dp[0][0][0] = 1;
	rep(i,n) rep(j,3210) rep(l,2) rep(m,b[i]+1)
		if (j+m<=k) (dp[i+1][j+m][l|(m==b[i])] += dp[i][j][l]) %= mod;
	rep(i,min(3333ll,k+1))
		(res += dp[n][i][1] + (i==k ? dp[n][i][0] : 0)) %= mod;
	cout << res << endl;
}