题目链接
这次的题目真的都还挺不错的，考的比较活
two times more这个关键信息告诉我们序列变化的规律，即为 2i2i 变换一次
于是我们可以考虑倍增
我们用 s[i]s[i] 来表示第1到i段(每一次变化称为一段)的数字和
ls1ls1 为奇数序列，ls2ls2 为偶数序列
lst1lst1 表示当前奇数序列的首项，lst2lst2 同理
假设现在计算第i段的值（假设是奇数段，偶数段同理）
我们就有：
- 首项：lst1lst1
- 末项：lst1+(2i−1)×2lst1+(2i−1)×2
- 项数：2i−12i−1
于是得到值为：
(lst1+2j−1−1)×2i−1(lst1+2j−1−1)×2i−1
预处理完之后我们就可以处理查询啦（与上面同理）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int MAXN = 61; ll l, r; ll p[MAXN], s[MAXN], l1[MAXN], l2[MAXN]; ll calc(ll x) { for (int i = 60; i >= 0; i--) { if (p[i] <= x) { if (i & 1) return (s[i] + ((l2[i] + x - p[i] - 1) % mod) * ((x - p[i]) % mod)) % mod; return (s[i] + ((l1[i] + x - p[i] - 1) % mod) * ((x - p[i]) % mod)) % mod; } } return 0; } void pre() { ll lst1 = 1, lst2 = 2; l1[0] = 1, l2[0] = 2; for (int i = 1; i <= 60; i++) { p[i] = p[i - 1] + (1ll << (i - 1)); if (i & 1) { s[i] = (s[i - 1] + ((lst1 + (1ll << i - 1) - 1) % mod) * ((1ll << i - 1) % mod)) % mod; lst1 += 1ll << i; } else { s[i] = (s[i - 1] + ((lst2 + (1ll << i - 1) - 1) % mod) * ((1ll << i - 1) % mod)) % mod; lst2 += 1ll << i; } l1[i] = lst1, l2[i] = lst2; } } int main() { pre(); cin >> l >> r; cout << ((calc(r) - calc(l - 1)) % mod + mod) % mod << endl; return 0; } |
