33OJ
登录 注册

#P17816. [ICPC 2019 Nanchang R] XOR Sum

    ID: 20415 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>数学2019数论中国剩余定理 CRT快速傅里叶变换 FFT位运算快速数论变换 NTTICPC拉格朗日插值法

[ICPC 2019 Nanchang R] XOR Sum

题目描述

序列 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n 的按位异或和定义为 a1⊕a2⊕⋯⊕ana_1 \oplus a_2 \oplus \cdots \oplus a_n,其中 ⊕\oplus 表示按位异或运算。

现在请你计算

∑k=1t∑i=xyf(i,k)\sum_{k=1}^{t}\sum_{i=x}^{y} f(i, k)

的值,其中 f(i,k)f(i,k) 是序列 1,2,3,⋯ ,ik−2,ik−1,ik1,2,3,\cdots,i^k-2,i^k-1,i^k 的按位异或和。

由于答案可能非常巨大,你只需要输出其对 (109+7)(10^9+7) 取模的结果。

输入格式

仅有一行包含三个整数 tt (1≤t≤100000)(1 \le t \le 100000)、xx 和 yy (1≤x≤y≤1018)(1 \le x\le y \le 10^{18}),含义如上所述。

输出格式

在一行中输出一个整数,表示答案对 (109+7)(10^9+7) 取模的结果。

1 2 7
15
3 2 7
363
7 2 7
358035

提示

翻译由 DeepSeek V4 Pro 完成