自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:18:36，当前版本为作者最后更新于2020-02-06 22:37:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Upd on 2020.10.7 修改一个小 typo。

题面传送门

Subtask $1$：没啥好说的，记得开 long long。

---

• 接下来的前置知识：有理数取模 P2613。

Subtask $2$：我们设问号的个数为 $y$，明显可以 $2^y$ 暴力枚举问号是 $\texttt{B\ or\ G}$，计算出符合条件的情况数 $x$，答案就是 $\large\frac{x}{2^y}$，对 $10^9+7$ 取模就行了。

时间复杂度：上界为 $\mathcal{O(2^n)}$。

---

• 接下来我们只讨论如何得到符合条件的情况数，前置知识：基础 DP。

Subtask $3$：考虑 $4$ 维 DP，$f_{i,j,k,p}$ 表示前 $i$ 位同学组成了 $j$ 个 $\texttt{GB}$，$k$ 个 $\texttt{BG}$，且当前位为 $p$（$p=0$ 时为 $\texttt{G}$，$p=1$ 时为 $\texttt{B}$）共有多少种情况，其中 $i\in[1,n],j\in[1,n],k\in[1,n],p\in\{0,1\}$。转移方程：

$$f_{i,j,k,0}=\begin{cases}0&s_i=\texttt{B}\\f_{i-1,j,k-1,1}&s_{i-1}=\texttt{B},s_i=\texttt{G}\\f_{i-1,j,k,0}&s_{i-1}=\texttt{G},s_i=\texttt{G}\\f_{i-1,j,k-1,1}+f_{i-1,j,k,0}&s_{i-1}=\texttt{?}\ ,s_i=\texttt{G}\end{cases} $$

$f_{i,j,k,1}$ 的转移方程和上面类似，不再赘述。

最后枚举所有 $j,k$，如果 $j\times a-k\times b\ge m$，情况数就加上 $f_{n,i,j,0}+f_{n,i,j,1}$。

时间复杂度：$\mathcal{O(n^3)}$。

---

• 下文中，我们设 $x$ 为 $\texttt{GB}$ 的个数，$y$ 为 $\texttt{BG}$ 的个数。

Subtask $4$：其实这个 Subtask 是引导你走向正解的（逃

该 Subtask 就是在求最后的 $x-y\ge m$ 共有多少种情况。

这就不由地让我们提出一个问题：$x$ 与 $y$ 到底有什么关系？它们的差的范围是多少？

如果你想到这个问题，那么恭喜你，你离 AC 本题不远了！

现在的你只需要挖掘出这个性质：在任何时刻，$|x-y|\leq 1$。

应该挺好理解的吧 qwq，举个例子：如果现在有一个转折点 $\texttt{BG}$，那么下一个转折点一定不可能是 $\texttt{BG}$，因为中间一定经过一个 $\texttt{GB}$ 的转折。说的再通俗一点，就是 $\texttt{BG.....BG}$ 的省略号中一定有 $\texttt{GB}$ 的转折。

所以这就引出了 Subtask $5$ 的解法：仍然是 $4$ 维 DP，$f_{i,j,k,p}$ 表示前 $i$ 位同学，$x$ 的值为 $j$，$x-y+1$ 的值为 $k$，且当前位为 $p$（$x,y,p$ 的定义上文有说明）共有多少种情况，其中 $i\in[1,n],j\in[1,n],k\in\{0,1,2\},p\in\{0,1\}$。

这样，时间复杂度就被我们压缩成了 $\mathcal{O(n^2)}$。

注意到空间只有 $8\texttt{MB}$，滚动数组优化一下即可。

感谢验题人 Isaunoya 倾情赞助的 std，因为出题人写的 std 锅掉了。

// powered by c++11
// by Isaunoya
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7 ;
int qpow(int x , int y) {
	int res = 1 ;
	for( ; y ; y >>= 1 , x = 1ll * x * x % mod)
		if(y & 1)
			res = 1ll * res * x % mod ;
	return res ;
}
int inv(int x) {
	return qpow(x , mod - 2) ;
}

int n , a , b ;
long long m ;
const int maxn = 2020 + 0202 ;
int arr[maxn] ;
int dp[2][maxn][3][2] ;
// i
// j * a
// -(j-k+1)
void del(int & x) {
	if(x >= mod) x -= mod ;
}
void addGB(int i) {
	int p = i & 1;
	for(int j = 0 ; j < i ; j ++)
		for(int k = 0 ; k < 2 ; k ++) {
			dp[p][j][k][0] += dp[p ^ 1][j][k + 1][1] ;
			del(dp[p][j][k][0]) ;
		}
}
void addBG(int i) {
	int p = i & 1;
	for(int j = 1 ; j < i ; j ++) 
		for(int k = 1 ; k < 3 ; k ++) {
			dp[p][j][k][1] += dp[p ^ 1][j - 1][k - 1][0] ;
			del(dp[p][j][k][1]) ;
		}
}
void addBB(int i) {
	int p = i & 1;
	for(int j = 0 ; j < i ; j ++)
		for(int k = 0 ; k < 3 ; k ++) {
			dp[p][j][k][1] += dp[p ^ 1][j][k][1] ;
			del(dp[p][j][k][1]) ;
		}
}
void addGG(int i) {
	int p = i & 1;
	for(int j = 0 ; j < i ; j ++)
		for(int k = 0 ; k < 3 ; k ++) {
			dp[p][j][k][0] += dp[p ^ 1][j][k][0] ;
			del(dp[p][j][k][0]) ;
		}
}

int main() {
// code begin.
	cin >> n >> m >> a >> b ;
	for(int i = 1 ; i <= n ; i ++) {
		char c ;
		cin >> c ;
		if(c == '?') arr[i] = 2 ;
		if(c == 'B') arr[i] = 1 ;
		if(c == 'G') arr[i] = 0 ;
	}
	if(arr[1] < 2) dp[1][0][1][arr[1]] = 1 ;
	else dp[1][0][1][1] = dp[1][0][1][0] = 1 ;
	for(int i = 2 ; i <= n ; i ++) {
		for(int j = 0 ; j < i ; j ++)
			for(int k = 0 ; k < 3 ; k ++)
				dp[i & 1][j][k][0] = dp[i & 1][j][k][1] = 0;
	// 0 - G
		if(arr[i] == 0 && arr[i - 1] == 0) addGG(i) ;
		if(arr[i] == 0 && arr[i - 1] == 1) addGB(i) ;
		if(arr[i] == 0 && arr[i - 1] == 2) addGG(i) , addGB(i) ;
	// 1 - B
		if(arr[i] == 1 && arr[i - 1] == 0) addBG(i) ;
		if(arr[i] == 1 && arr[i - 1] == 1) addBB(i) ;
		if(arr[i] == 1 && arr[i - 1] == 2) addBB(i) , addBG(i) ;
	// 2 - ?
		if(arr[i] == 2 && arr[i - 1] == 0) addGG(i) , addBG(i) ; // ?G
		if(arr[i] == 2 && arr[i - 1] == 1) addBB(i) , addGB(i) ; // ?B
		if(arr[i] == 2 && arr[i - 1] == 2) { // ??
			addBG(i) , addBB(i) ;
			addGB(i) , addGG(i) ;
		}
	}
	int cnt = 0 ;
	for(int i = 1 ; i <= n ; i ++)
		if(arr[i] == 2) ++ cnt ;
	int ans = 0 ;
	for(int j = 0 ; j <= n ; j ++) 
		for(int k = 0 ; k < 3 ; k ++) {
			if(1ll * j * a - 1ll * (j - k + 1) * b >= m) {
				ans += dp[n & 1][j][k][0] ;
				del(ans) ;
				ans += dp[n & 1][j][k][1] ;
				del(ans) ;
			}
		}
	cout << 1ll * ans * inv(qpow(2 , cnt)) % mod << '\n' ;
	return 0 ;
// code end.
}