LGPP4067口胡

直接计算太困难了，考虑转化。

可以转化为原储能表的和减去原储能表中不大于 /(k/) 的部分，然后减去数量乘上 /(k/) 即可。零次和与一次和可以同时统计。

原储能表的元素和非常好算啊，直接拆位即可，复杂度 /(O(/log n)/)。

我们假设存在一个 /(t/) 满足 /(2^{t-1}<k/leq 2^t/)。

将行列分为长度为 /(2^t/) 的若干段，发现每一行只有第 /(i/) 行对应第 /(i/) 列才有可能小于 /(k/)。（因为只有此时高位异或才为 /(0/)）

而让一个数去异或 /([0,2^t-1]/) 中的所有数，得到的结果一定还是 /([0,2^t-1]/) 中的所有数（对于 /(a/ne b/) 有 /(a/texttt{ xor } x/ne b/texttt{ xor } x/)）。于是只要两端中有一段是整的那么贡献都非常好算。

我们还需要考虑的是不完整的段对不完整的段的贡献。

长度不是 /(2/) 的幂好像就没有优秀的性质了，于是我们直接把这两段都拆成 /(/log k/) 段长度为 /(2/) 的幂的段。

考虑两个区间 /([a/times 2^x,(a+1)/times 2^x-1]/) 和 /([b/times 2^y,(b+1)/times 2^y-1]/) 的答案。（方便计算有 /(x>y/)）

如果高位异或起来大于 /(k/) 的对应的高位，那么贡献显然为 /(0/)。

如果高位异或起来小于 /(k/) 的对应的高位那么贡献显然是 /(2^{x+y}/)。

考虑到 /(b/) 的 /([y,x-1]/) 位异或到第一个区间上其实是没有任何影响的（因为原本是哪些数那还是哪些数），剩下的部分的贡献就是 /((k/bmod 2^{x})/times 2^y/)。