Codeforces 1062C Banh-mi题解

思路:
每 次 吃 x i 最 大 的 食 物 每次吃x_i最大的食物 xi

假 设 初 始 区 间 内 有 a 个 1 , b 个 0 , 那 么 先 吃 完 所 有 初 始 美 味 为 1 的 食 物 , 得 到 喜 悦 程 度 为 2 a − 1 假设初始区间内有a个1,b个 0,那么先吃完所有初始美味为1的食物,得到喜悦程度为2^a-1 a1b012a1

人后剩下的就是初始美味为0的食物,现在美味度为
2 a − 1 2^a-1 2a1
所以吃完这些喜悦度就是
( 2 a − 1 ) ( 2 b − 1 ) (2^a-1)(2^b-1) (2a1)(2b1)
然后通过前缀和求出任意区间01数目,利用快速幂求下式即可
( 2 a − 1 ) 2 b (2^a-1)2^b (2a1)2b

#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int n, q;
char s[maxn];
int c[2][maxn];
ll fpow(ll a, ll n)
{
   
	ll res = 1, base = a % mod;
	while (n)
	{
   
		if (n & 1) res *= base, res %= mod;
		base *= base, base %= mod;
		n >>= 1;
	}
	return res % mod;
}
int main(void){
   
	scanf("%d %d", &n, &q);
	scanf("%s", s + 1);
	c[0][0] = c[1][0] = 0;
	for (int i = 1, x; i <= n; i++)
	{
   
		x = s[i] - '0';
		c[x][i] = c[x][i - 1] + 1;
		c[x ^ 1][i] = c[x ^ 1][i - 1];
	}
	for (int i = 1, l, r; i <= q; i++)
	{
   
		scanf("%d %d", &l, &r);
		ll a = c[1][r] - c[1][l - 1], b = c[0][r] - c[0][l - 1];
		printf("%lld\n", (fpow(2, a + b) - fpow(2, b) + mod) % mod);
	}
	return 0;
}