1 条题解
-
0
20pts
求解出每个位置的权值,对于每次询问 输出。
40pts
首先注意到每一位是独立的。
如果用第 行来计算 , 对 的贡献系数是 .
对于 ,可以利用 lucas 定理知道 $\binom{n}{k} \mod 2 = \binom{n / 2}{k / 2} \times \binom{n \% 2}{k \% 2}$.
其实就是要求 总是为 ,才能使得 为 .
也就是 应当是 的子集,所以有贡献的位置仅有 个,至此我们可以通过枚举子集得到一个 的单次做法。
因为数据随机生成,复杂度为 ,可以通过。
100pts
那么更一般的,我们可以用第 行来计算 ,对于 对 的贡献系数是 ,这启发我们可以令 .
通过预处理 行,我们可以得到一个 的单次做法.
总复杂度 可以通过本题(其中 )。
- 1
信息
- ID
- 144
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者