Codeforces Round #674 (Div. 3)

https://codeforces.com/contest/1426/problem/F

题意

给出一个字符串，其中只包含 \(a,b,c,?\)，其中 \(?\)可以换成 \(a,b,c\)中任意一个字母，问所有可能的序列中子序列 \(abc\) (可以不连续)的出现次数。

思路

我们只需要扫一遍序列并同时维护 序列数量(遇到一个 \(?\) 序列数量变为 \(3\) 倍)、子序列 \(a\) 数量、子序列 \(ab\) 数量和子序列 \(abc\) 数量 这四个变量即可。

我们用 \(dp[0]\) 、\(dp[1]\) 、\(dp[2]\) 、\(dp[3]\) 分别表示序列数量、子序列 \(a\) 数量、子序列 \(ab\) 数量和子序列 \(abc\) 数量。

• 当遇到 \(a\) 时，\(a\)序列数量需要加上全面出现过的序列总数，即: \(dp[1] = dp[0] + dp[1]\) 。
• 当遇到 \(b\) 时，\(ab\)序列数量需要加上前面出现过的 \(a\) 序列的总数，因为此时出现的 \(b\) 可以和以前出现的任意一个 \(a\) 组成 \(ab\) 序列，即: \(dp[2] = dp[2] + dp[1]\) 。
• 当遇到 \(c\) 时，同上更新，即: \(dp[3] = dp[3] + dp[2]\) 。
• 当遇到 \(?\) 时，由于 \(?\) 可以换成其他三种字母中的任意一个，所以相应序列都会变成 \(3\) 倍，如下:
  • \(abc\) 序列在 \(?\) 变成 \(a 或 b\) 时都会对 \(dp[3]\) 有一个 \(dp[3]\) 的贡献，但是 \(?\) 变成 \(c\)，则会对 \(dp[3]\) 造成 \(dp[3] + dp[2]\) 的贡献，因为 \(c\)可以和前面任意一个 \(ab\) 子序列组成 \(abc\)，故转移方程为: \(dp[3] = dp[3] * 3 + dp[2]\) 。
  • \(ab\) 序列的变化同上，\(?\) 变成 \(a 或 c\) 时都会对 \(dp[2]\) 有一个 \(dp[2]\) 的贡献，但是 \(?\) 变成 \(b\)，则会对 \(dp[2]\) 造成 \(dp[2] + dp[1]\) 的贡献，因为 \(b\) 可以和前面任意一个 \(a\) 子序列组成 \(ab\)，故方程为: \(dp[2] = dp[2] * 3 + dp[1]\) 。
  • \(a\) 序列同理: \(dp[1] = 3 * dp[1] + dp[0]\) 。
  • 同时序列总数乘 \(3\) : \(dp[0] = 3 * dp[0]\) 。
  • 上面相应的数量关系一定要按顺序更新。

注意运算时取模

Code

/*---------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（′<_｀ ）　 
　　　　 （ ′_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__?つ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　?
--------------------------------------------------------------*/
#include<bits/stdc++.h>
#define IO  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define req(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back		
#define fi first
#define se second
#define PI pair<int,int>
#define PII pair<ll,PI>

using namespace std;

typedef long long ll;
const int N = 2e5 + 7;
const ll mod = 1e9 + 7;

inline ll read(){
    ll x=0;
    int f=1;
    char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){
        if(ch==‘-‘)
            f=-1;
        ch=getchar();
    }
    while(ch>=‘0‘&&ch<=‘9‘){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void print(ll x){
	if(x<0)putchar(‘-‘),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}
char s[N];
ll dp[4];

void slove(){
	ll n;
	n = read();
	scanf("%s",s + 1); 
	dp[0] = 1;
	for (int i = 1; i <= n; ++i)
	{ 
		if (s[i] == ‘a‘)
		{
			dp[1] = (dp[1] + dp[0]) % mod;
		}else if(s[i] == ‘b‘){
			dp[2] = (dp[2] + dp[1]) % mod;
		}else if(s[i] == ‘c‘){
			dp[3] = (dp[3] + dp[2]) % mod;
		}else{
			dp[3] = (3 * dp[3] % mod + dp[2]) % mod;
			dp[2] = (3 * dp[2] % mod + dp[1]) % mod;
			dp[1] = (3 * dp[1] % mod + dp[0]) % mod;
			dp[0] = 3 * dp[0] % mod;
		}
	}
	print(dp[3]);
	puts("");
}

int main()
{

	#ifdef ONLINE_JUDGE
   	#else
   	freopen("1.in", "r", stdin);
   	//freopen("1.out", "w", stdout);
   	#endif 
	int t = 1;
	// t = read();
	while(t--){
		slove();	
	}
	return 0;
} 
``

F. Number of Subsequences(Codeforces Round #674 (Div. 3))