> 在看题解前，建议自己先尝试分析本题，个人认为还是挺有意义的
题目分析
根据汉明距离的定义:
dH(x,y)=∑i=0∞I((x&2i)≠(y&2i))d_H(x,y)=\sum_{i=0}^{\infty}I((x\&2^i)\neq(y\&2^i)) dH (x,y)=i=0∑∞ I((x&2i)=(y&2i))
不难得出，题目大意就是在求区间 [0,n][0,n][0,n] 内有多少个数对 (x,y)(x,y)(x,y) 满足：0≤x<y≤n, dH(x,y)≤k0\le x<y\le n,\ d_H(x,y)\le k0≤x<y≤n, dH (x,y)≤k。
如果直接暴力，在 n≤106n\le 10^6n≤106 的条件下一定超时，但在 10610^6106 的情况下，不难发现如果按位统计二进制位上的 111 的个数，不仅可以计算数对间的汉明距离，也只需要 O(∣n∣)\mathcal{O}(|n|)O(∣n∣) 的复杂度，再加上二进制位运算与杨辉三角（组合数）的优化，完全可以在 O(t)\mathcal{O}(t)O(t) 的时间复杂度下跑完。
因为要求统计汉明距离 dH≤kd_H\le kdH ≤k 的方案数，可以想到运用组合数来进行快速计算，又由于每一次都是统计从 000 至 nnn 的情况，可以通过预处理组合数的前缀和来实现 O(1)\mathcal{O}(1)O(1) 查询。
前置芝士
组合数学
组合：从n个不同元素中取出 m（m≤n）m（m\le n）m（m≤n） 个元素并成一组，不考虑顺序的方案数用符号 CnmC_n^mCnm 或 (nm)\binom{n}{m}(mn ) 表示。
组合数杨辉三角优化
递推公式：(nm)=(n−1m−1)+(n−1m)\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}(mn )=(m−1n−1 )+(mn−1 )。
其实也不能算是优化。
前缀和
这应该不用说了吧。
模逆元
为了实现正确计算在模运算下的除法计算，需要使用对应模逆元的乘法来达成（参考模反元素）。
代码实现
看着思路很简单，可是我好几个小时的成果，QwQ，若哪里思路错了或没讲清楚，勿喷。
最后，为什么这只是一道黄题，蚌埠住了，还以为至少是绿起步，QwQ。
