ABC129 - aizuzia

桁 DP 書けないマンです。

Problems

A, B, C: はい
D: 累積和取ろうとしたけどめんどくなって Union-Find に逃げた

E

解説と同じ考察によって、求める答えは $f(L) = \sum_{i = 0}^{L} 2^{popcount(i)}$ であることがわかる。桁 DP っぽいけど普通に分かんないんだが？？？

最上位桁で $i$ を分類することを考える。 $g(a, b) = \sum_{i = a}^{b} 2^{popcount(i)}$ として、 $L = 1xx..xx$ のとき $g(0, L) = g(000..00, 011..11) + g(100..00, 1xx..xx)$ になる。前者は $|L| - 1$ 桁のすべての数について足せばいいので簡単になって、 $i$ ビット立っている $n$ 桁の数は $\binom{n}{i}$ 個。後者は最上位桁の自由度が $2$ 通りあり、下の桁は再帰的に求まるので、合わせると $g(0, L) = \sum_{i = 0}^{|L|-1}{\binom{|L|-1}{i} \times 2 ^ i} + 2 \times g(xx..xx)$ になる。 $L = 0xx..xx$ のときは単に $f(0xx..xx) = f(xx..xx)$ なのでやっぱり再帰的にいける。 $O(|L|)$ 。

と思って書き始めてから気づいたけど、 $\sum_{i = 0}^{|L|-1}{\binom{|L|-1}{i} \times 2 ^ i}$ のところで $L$ 以下のすべての $\binom{n}{m}$ が必要になるのでやっぱりダメだった。いやこの形綺麗だし、なんか公式あるんでは？って思って wikipedia を漁ったら $\sum_{i = 0}^{n}{\binom{n}{i} \times x ^ i} = (1 + x) ^ k$ らしく、計算量が落ちて通った。え、これほんとに想定解法？？？