Contest Info

date: 2018.09.08 12:00-17:00

practice link

Solutions

H. Hamming Weight

题目大意：定义 \(h(x)=\text{popcount}(x)\)，求 \(\sum_{i=1}^{N}\sum_{j=1}^{N}h(i\text{&}j)\)。输入输出均用二进制表示。\(N\) 有 \(n\) 位。

题解：显然答案为 \(\sum_{i=0}^{n-1}f(i)^{2}\)，其中 \(f(i)\) 表示 \(1\sim N\) 中第 \(i\) 位（低位起）为 \(1\) 的数的个数。容易想到一个数位 \(dp\) 来求解（按照套路先把 \(N\) 加一）： \[ f(i)=\begin{cases} &2^{i}\lfloor\frac{N}{2^{i+1}}\rfloor&(N_{i}=0)\\ &2^{i}\lfloor\frac{N}{2^{i+1}}\rfloor+(N\mod{2^{i}})&(N_{i}=1) \end{cases} \] 但是这样 \(N_{i}=1\) 的情况不是很好算（也差不多），我们把它变一下形：\(N-2^{i}\lfloor\frac{N}{2^{i+1}}\rfloor-2^{i}\)。

这样之后，答案就变成了 \(h(N)N^{2}+\sum_{i=0}^{n-1}\left((2^{i}\lfloor\frac{N}{2^{i+1}}\rfloor)^{2}+\left(2^{2i}-2^{i+1}N\lfloor\frac{N}{2^{i+1}}\rfloor-2^{i+1}N+2^{2i+1}\lfloor\frac{N}{2^{i+1}}\rfloor\right)[N_{i}=1]\right)\)

考虑每一项的计算：

其中第五项等于 \(-2N^{2}\)，第六项等于 \(\displaystyle{\frac{N^{2}-\sum_{i=0}^{N-1}2^{2i}[N_{i}=1]}{2}}\)，因此第一、三、五、六项的和为 \((h(N)-\frac{3}{2})N^{2}+\frac{1}{2}\sum_{i=0}^{N-1}2^{2i}[N_{i}=1]\)，左边很容易用 \(FFT\) 计算，右边 \(\mathcal{O}(n)\) 即可。

对于 \(\sum_{i=0}^{n-1}(2^{i}\lfloor\frac{N}{2^{i+1}}\rfloor)^{2}\)，我们考虑 \(N\) 中的任意两个 \(1\) 对答案有多少贡献，容易发现答案为 \(\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[N_{i}=N_{j}=1]2^{i+j-2}\min\{i,j\}\)，这有点像一个卷积形式，我们做一个变形，\(\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[N_{i}=N_{j}=1]2^{i+j-2}(2i[i< j]+i[i=j])\)，这样用分治 \(FFT\) 即可 \(\mathcal{O}(n\log^{2}n)\) 计算出答案。

最后考虑 \(-\sum_{i=0}^{n-1}2^{i+1}N\lfloor\frac{N}{2^{i+1}}\rfloor\) 的计算，这个事实上比较简单，画一下可以发现 \(\sum_{i=0}^{n-1}2^{i+1}\lfloor\frac{N}{2^{i+1}}\rfloor\) 可以用前缀和 \(\mathcal{O}(n)\) 计算，然后 \(FFT\) 乘一下即可。

时间复杂度 \(\mathcal{O}(n\log^{2}n)\)。