题意

·给定T个01字符串str和对应的重复次数n,求 str重复n次后的字符串的单调不增子串的数量

分析

一般情况

我们先考虑不重复(n = 1)的情况

·我们知道对01字符串的单调不增子串，那其只有可能为 全0、左边全0右边全1或全1

全0、左边全0右边全1

·对全0、左边全0右边全1的情况，我们可以知道其必然有一位为最右边的0，若子串的最右边的0不同，则其为不同的子串

·而对一个最右的0，我们先选下这个最右的0，其要构成一个单调不增子串，则其左边只有选0，右边只有选1

·而除了定了的最右的0，其余的位都是可取可不取的(最右的0的选定保证了不会重复)

·所以对每一个0，以其为最右0的子串数量为 2 ^ (左边0数 + 右边1数)

·所以对这种情况，我们只要枚举每个0，加上 2 ^ (左边0数 + 右边1数)

·高效求左右边的01数量我们可以先预处理一个前缀和数组来存到哪一位左边的1的总数(0的数量用当前位置减前缀和即可)

·高效求2 ^ x, 我们可以预处理一个pow2[]数组

·前缀和

		ll num = 0;
		for (int i = 1; i <= cnt; i ++ )
		{
			if (str[i] == '1') continue;
			ll pre_0 = i - S[i] - 1, back_1 = S[cnt] - S[i]; // 左边的0和右边的1的数量
			ll k = pre_0 + back_1;
			if (k < N) num = (num + pow2[k]) % mod; // 用预处理的pow2[]优化
			else num = (num + qmi(2, k)) % mod; // 为保险在pow2范围外时用快速幂
		}

·pow2初始化

void init_pow2()
{
	pow2[0] = 1;
	for (int i = 1; i < N; i ++ )
	{
		pow2[i] = pow2[i - 1] * 2 % mod; 
	}
}

全1

·对全1的情况，我们可以把它认为是选了个最前面的虚拟最右0的情况

·注意1不能全不选(否则为空串)

·所以总数为 2 ^ (1数) - 1

考虑重复的情况

·首先我们知道重复n次后的字符串本质上就是“一般情况”，但是对 n <= 10 ^ 18显然直接暴力会超时

·我们考虑对重复n次的字符串中的一个字符串单元的一个0

·不妨设这个单元是第i个, 该最右0的位置为j，与“一般情况左边全0右边全1”的思路相同

·我们设每个单元的0的总数为 sum_0, 1的总数为sum_1,单元内，该0左侧0个数为pre_0[j]、右侧1个数为back_1[j]

·则该0的满足条件的子串数为

2 ^ (sum_0 * (i - 1) + pre_0[j] + back_1[j] + (n - i) (本质上就是左边的所有0 + 右边的所有1）

·所以可以得知左边全0右边全1的子序列总数为

·所以我们只需要按推出的式子将每个部分用求出来再乘在一起就行了(

·左式 (\sum_{i}的部分)

		ll sum_0 = cnt - S[cnt], sum_1 = S[cnt];
		ll fac = qmi(2, (sum_0 - sum_1 + pow_mod) % pow_mod); //即式子中 phi 值
		ll mul; // 最后的数
		if (sum_0 == sum_1) mul = n % mod; // 相等时为n (注意要取模，n的范围太大了)
		else mul = ((qmi(fac, (n + 1) % pow_mod) - fac + mod) % mod) * qmi(fac - 1, mod - 2) % mod; // 不相等时按等比数列求和 (千万注意快速幂的指数要多取模、取模补到正数，指数为负会爆TLE)

·中间式即为一般情况的一个单元中的“左边全0右边全1”的数量

·右式

		ll exp_tmp = ((n % pow_mod) * (sum_1 % pow_mod) - (sum_0 % pow_mod)) % pow_mod;
		if (exp_tmp < 0) exp_tmp += pow_mod; // (防指数为负）
		ll tmp = qmi(2, exp_tmp);

·最后像“一般情况”一样， 加上全一的情况即可， 即 2 ^ (n * sum_1) - 1.

		ll exp_last = (S[cnt] + ((n - 1) % pow_mod) * (sum_1 % pow_mod)) % pow_mod;
		ans = (ans + qmi(2, exp_last) - 1 + mod) % mod;

tips

·快速幂要注意指数不能为负！(因为这个爆TLE卡了好久)；

·多取模，虽然会降低可读性(,但n 10^18 的数量级还是太权威了；

·指数过大要取模 mod - 1, 费马小定理可证明在 mod 为质数(1e9 + 7为质数) 时同模 

ll qmi(ll a, ll b)
{
	a %= mod;
	b %= mod - 1; // 指数取模
	ll res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1; 
	}
	return res; 
}

复杂度

时间复杂度 O(T * m) (m为每次输入的字符串长度), 空间复杂度 O(m)。

完整代码

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring> 
#include <algorithm>

using namespace std;
const int N = 200010, mod = 1e9 + 7;
typedef long long ll;

ll n; 
ll S[N]; // 1 的个数的前缀和 
ll pow_mod = mod - 1;
string str; 
int cnt;
ll ans;
ll pow2[N]; 

ll qmi(ll a, ll b)
{
	a %= mod;
	b %= mod - 1;
	ll res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1; 
	}
	return res; 
}

void init_pow2()
{
	pow2[0] = 1;
	for (int i = 1; i < N; i ++ )
	{
		pow2[i] = pow2[i - 1] * 2 % mod; 
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin >> T;
	init_pow2();
	
	while (T -- )
	{
		cin >> n;
		ans = 0;
		cin >> str;
		str = " " + str;
		S[0] = 0;
		ans = 0;
		cnt = str.size() - 1;
		for (int i = 1; i <= cnt; i ++ )
		{
			S[i] = S[i - 1];
			if (str[i] == '1') S[i] ++ ;
		} 
		ll sum_0 = cnt - S[cnt], sum_1 = S[cnt];
		ll fac = qmi(2, (sum_0 - sum_1 + pow_mod) % pow_mod);
		ll mul;
		if (sum_0 == sum_1) mul = n % mod;
		else mul = ((qmi(fac, (n + 1) % pow_mod) - fac + mod) % mod) * qmi(fac - 1, mod - 2) % mod;

		ll exp_tmp = ((n % pow_mod) * (sum_1 % pow_mod) - (sum_0 % pow_mod)) % pow_mod;
		if (exp_tmp < 0) exp_tmp += pow_mod;
		ll tmp = qmi(2, exp_tmp);
//		printf("%lld %lld %lld --- \n", fac, tmp, mul);
		ll num = 0;
		for (int i = 1; i <= cnt; i ++ )
		{
			if (str[i] == '1') continue;
			ll pre_0 = i - S[i] - 1, back_1 = S[cnt] - S[i];
			ll k = pre_0 + back_1;
			if (k < N) num = (num + pow2[k]) % mod;
			else num = (num + qmi(2, k)) % mod;
		}
//		printf("%lld --- \n", num);
		
		ans = (ans + tmp * mul % mod * num) % mod;
		ll exp_last = (S[cnt] + ((n - 1) % pow_mod) * (sum_1 % pow_mod)) % pow_mod;
		ans = (ans + qmi(2, exp_last) - 1 + mod) % mod; 
		cout << ans << '\n';
	}
	
	return 0;
 }

·希望对大家有所帮组qwq.