arc116D

题意很简洁。

让你求有多少个长度为 \(N\) 的序列 \(A\)，使得 \(\sum_{i=1}^{n}A_i=m,\sum_{\oplus}A_i=0\).

---

暴力 dp 效率不高。

考虑异或的性质，我们本质上时在填一个 \(n\) 行，\(\lceil\log_2 m\rceil\) 列的表。

只需要保证 每一列的 1 的个数符合题意，并且和是正确的即可。

那么很容易得到 dp: \[ \text{dp}_n(x)=\sum_{k=0,2\mid k}\binom{n}{k}\text{dp}_{n-1}(x-2^nk) \]

假设 \(n,m\) 同阶复杂度 \(\mathcal{O(n^2)}\)。

可以考虑运算次数：

\[\sum_{j=1}^{\log_2 m}\sum_{i=1}^{m}\min(\frac{i}{2^j},n)\]

若 \(n>m\) 那么 \(\dfrac{i}{2^j}\leq n\)。

所以原式小于等于

\[\sum_{j=1}^{\log_2 m}\sum_{i=1}^{m}\frac{i}{2^j}=\sum_{j=1}^{\log_2 m}\frac{1}{2^j}\sum_{i=1}^{m}i=\sum_{j=1}^{\log_2 m}\frac{1}{2^j}m^2=\mathcal{O(m^2)}\]

即 \(\mathcal{O(n^2)}\)

代码可见 code