题意：给出 ，求 答案对
取模，，实现 。
为了方便，将 的限制改为
。
异或在数论中的性质很差，不能先对
函数下手。异或和位有关，不妨先从位的角度思考。
发现若 ，那么 恰好把 以内的所有数取到 次。即
若有了
的影响，后 位仍然恰把 以内的所有数取到 次。高位会被指定，相当于求 的区间和。
考虑 且 的情形。不难发现 会把 以内的数都取到 次。即 若有了
的影响，后 位仍然恰把 以内的所有数取到 次。高位会被指定，相当于求 的区间和。
若 不是 的整幂，则可以采用类似数位 的技巧，将答案划分成若干个
“钦定部分高位，其余低位随意” 的求和。
会划分出 个 的区间和。
而众所周知
的前缀和可以一个根号求出，复杂度即为 。
事实上，本质不同的询问并不多。
考虑我们“钦定若干高位”是怎样做的，肯定是卡住 或 的上界。
而高位的个数只有 ，也就只有
种钦定的方法。
记忆化一下就做到 了。