本题可能包含常规算法竞赛中不包含的技巧，大家做题时适当娱乐即可
对一个 64 位无符号整数 x，将其二进制从 低位到高位 编号为 0, 1, 2, ..., 63。
对于给定的正整数 k，我们定义：
- 若
x的二进制表示中存在从低位到高位第 k 个1，则答案为该1所在的位编号； - 若不存在第
k个1，则答案为64。
你需要根据给定规则生成大量 (x, k)，并计算每个查询的答案，输出所有答案的总和。
输入格式
输入只给出询问个数 $n$ 与伪随机数种子 $seed$。你需要用伪随机数种子生成所有的询问。具体生成方式见参考代码
输出格式
输出一个非负整数，表示 $n$ 组询问答案的总和。
样例
input
2048 60576
output
100000
参考代码
你可以基于这份代码完成你的解题，你只需要补全 query 函数即可。如果需要，你也可以进行任意的修改。
#include<iostream>
int n;
using u64 = unsigned long long;
u64 seed, ans = 0;
u64 next(u64 & x) {
x ^= x << 13; x ^= x >> 17; x ^= x << 5;
return x;
}
int query(u64 x, int k) {
}
int main() {
std::cin >> n >> seed;
for(int i = 0;i < n;++i) {
u64 x = next(seed);
int k = (next(seed) & 63) + 1;
ans += query(x, k);
}
std::cout << ans << '\n';
}子任务
Subtasks
- Subtask 1 (0 Points): $1 \le n \le 10^5$
- Subtask 2 (1 Point): $1 \le n \le 10^8$
- Subtask 3 (7 Points): $1 \le n \le 2\times 10^8$
- Subtask 4 (8 Points): $1 \le n \le 3\times 10^8$
- Subtask 5 (9 Points): $1 \le n \le 4\times 10^8$
- Subtask 6 (10 Points): $1 \le n \le 5\times 10^8$
- Subtask 7 (11 Points): $1 \le n \le 6\times 10^8$
- Subtask 8 (12 Points): $1 \le n \le 7\times 10^8$
- Subtask 9 (13 Points): $1 \le n \le 8\times 10^8$
- Subtask 10 (14 Points): $1 \le n \le 9\times 10^8$
- Subtask 11 (15 Points): $1 \le n \le 10^9$