二进制小数
我们得到了一个长度为n的二进制字符串S，其中每个字符要么是"1"要么是"0">。
我们被要求对字符串执行几个查询。
在每个查询中，我们都得到了L和R的整数。我们必须告诉S[l.r]子字符串的值，用十进制表示。
示例测试用例：
Input:
1011 (string S)
5 (number of queries)
1 1 (l, r)
2 2
1 2
2 4
1 4
Output:
1 (1 * 2^0 == 1)
0
2
3 (0 * 2^2 + 1 * 2^1 + 1 * 2^0)
11 (1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 = 11)
限制
1 < N < 10^5
1 < Q < 10^5
由于数字可能非常大，我们需要以模10^9+7打印它。
方法
因此，基本上我们需要将二进制表示的子字符串S[l.r]转换为十进制。
I预先计算阵列B中所有I:[0，n-1]的S[I…n-1]结果。所以现在B[i]表示子字符串S[i.n-1]的十进制数表示
vector<int> pow(1e5, 1);
for(int i = 1; i < 1e5; i++) {
pow[i] = (pow[i - 1] * 2) % mod;
}
string s;
getline(cin, s);
vector<int> B(n, 0);
int prev = 0;
for(int i = 0; i < n; i++) {
B[(n - 1) - i] = (prev + (s[(n - 1) - i] == '1' ? pow[i] : 0)) % mod;
prev = B[(n - 1) - i];
}
while(q--) {
int l, r;
cin >> l >> r;
cout << ((B[l] - (r + 1 < n ? B[r + 1] : 0) + mod) % mod) / pow[n - (r + 1)]<< "n";
}
return 0;
使用上述方法，只有样本测试用例通过，所有其他用例都给出了错误答案(WA(。
我甚至尝试使用分段树来解决这个问题，但这也不起作用。
解决这个问题的正确方法是什么？
将V[k]定义为从k开始的S的数字值。
然后是子串CCD_ 4。(类似的事情，我可能有一个错误。用小例子玩。(
关于10^9 + 7，有用的事实是它是素数。(第一个10位数的素数。(这意味着除以2等于乘以2^(10^9 + 5)。这是一个常数，你可以通过反复求平方来算出。并且使用重复平方可以非常有效地将该常数提高到高功率。
有了这个，您可以为V创建一个查找表，然后在时间O(log(n))中执行查询。
这似乎与常规和范围查询相同，只是(1(我们需要存储部分和mod 10^9+7，(2(在检索过程中，我们需要"移位"；全部金额的相关部分乘以其右侧部分的长度。致"；移位"；在这种情况下意味着乘以2^(length_of_fsuffix(mod 10^9+7。当然，求和的部分mod 10^9+7。
但是btilly的答案似乎要简单得多：(