洛谷题面

题目大意

给你一个字符串，只包含 A,B,C,?， 其中 ? 表示 A,B,C 中的任意一个，问在所有可能的 A,B,C 的字符串中，总共有多少长度为 \(3\) 的子序列是 <'A', 'B', 'C'>。

题目分析

考虑动态规划。

令 \(dp[i][j]\) 表示前 \(i\) 个字符中形成 A,B,C 的前 \(j\) 项的字串数量。

其中 \(0\le i\le 3\)，当 \(i=0\) 时无实际意义，只用来计数。

初始化 \(dp[1][0]=1\)。

如果当前字符是 ?，那么根据乘法原理，我们直接乘上 \(3\) 更新状态：

for(register int j=0;j<=3;j++)
{
	dp[i+1][j]=(dp[i+1][j]+dp[i][j]*3)%mod;//乘上 3
}

如果不是，那么普通加减即可：

for(register int j=0;j<=3;j++)
{
	dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
}

代码

//2021/9/8

//2021/9/9

#include <iostream>

#include <cstdio>

#include <cstring>

#define int long long 

#define debug(c) cerr<<#c<<" = "<<c<<endl

#define cek() puts("qwq")

namespace Newstd
{
	inline int read()
	{
		char c;
		bool flag=false;
		while((c=getchar())<'0' || c>'9')
		{
		    if(c=='-') flag=true;
		}
		int res=c-'0';
		while((c=getchar())>='0' && c<='9')
		{
		    res=(res<<3)+(res<<1)+c-'0';
		}
		return flag?-res:res;
	}
	inline void print(int x)
	{
		if(x<0)
		{
			putchar('-');x=-x;
		}
		if(x>9)
		{
			print(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int ma=100005;

const int mod=1e9+7;

char s[ma];

int dp[ma][4];

#undef int

int main(void)
{
	#define int long long 
	
	scanf("%s",s+1);
	
	int n=strlen(s+1);
	
	dp[1][0]=1ll;
	
	for(register int i=1;i<=n;i++)
	{
		if(s[i]=='?')
		{
			for(register int j=0;j<=3;j++)
			{
				dp[i+1][j]=(dp[i+1][j]+dp[i][j]*3)%mod;
			}
		}
		
		else
		{
			for(register int j=0;j<=3;j++)
			{
				dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
			}
		}
		
		if(s[i]=='A')
		{
			dp[i+1][1]=(dp[i+1][1]+dp[i][0])%mod;
		}
		
		else if(s[i]=='B')
		{
			dp[i+1][2]=(dp[i+1][2]+dp[i][1])%mod;
		}
		
		else if(s[i]=='C')
		{
			dp[i+1][3]=(dp[i+1][3]+dp[i][2])%mod;
		} 
		
		else
		{
			dp[i+1][1]=(dp[i+1][1]+dp[i][0])%mod;
			
			dp[i+1][2]=(dp[i+1][2]+dp[i][1])%mod;
			
			dp[i+1][3]=(dp[i+1][3]+dp[i][2])%mod;
		}
	}
	
	printf("%lld\n",dp[n+1][3]);
	
	return 0; 
}