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