【Codeforces 1426 F】Number of Subsequences，字符串计数DP

problem

F. Number of Subsequences
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a string s consisting of lowercase Latin letters “a”, “b” and “c” and question marks “?”.

Let the number of question marks in the string s be k. Let’s replace each question mark with one of the letters “a”, “b” and “c”. Here we can obtain all 3k possible strings consisting only of letters “a”, “b” and “c”. For example, if s=“ac?b?c” then we can obtain the following strings: [“acabac”, “acabbc”, “acabcc”, “acbbac”, “acbbbc”, “acbbcc”, “accbac”, “accbbc”, “accbcc”].

Your task is to count the total number of subsequences “abc” in all resulting strings. Since the answer can be very large, print it modulo 109+7.

A subsequence of the string t is such a sequence that can be derived from the string t after removing some (possibly, zero) number of letters without changing the order of remaining letters. For example, the string “baacbc” contains two subsequences “abc” — a subsequence consisting of letters at positions (2,5,6) and a subsequence consisting of letters at positions (3,5,6).

Input
The first line of the input contains one integer n (3≤n≤200000) — the length of s.

The second line of the input contains the string s of length n consisting of lowercase Latin letters “a”, “b” and “c” and question marks"?".

Output
Print the total number of subsequences “abc” in all strings you can obtain if you replace all question marks with letters “a”, “b” and “c”, modulo 109+7.

Examples
inputCopy
6
ac?b?c
outputCopy
24
inputCopy
7
???
outputCopy
2835
inputCopy
9
cccbbbaaa
outputCopy
0
inputCopy
5
a???c
outputCopy
46
Note
In the first example, we can obtain 9 strings:

“acabac” — there are 2 subsequences “abc”,
“acabbc” — there are 4 subsequences “abc”,
“acabcc” — there are 4 subsequences “abc”,
“acbbac” — there are 2 subsequences “abc”,
“acbbbc” — there are 3 subsequences “abc”,
“acbbcc” — there are 4 subsequences “abc”,
“accbac” — there is 1 subsequence “abc”,
“accbbc” — there are 2 subsequences “abc”,
“accbcc” — there are 2 subsequences “abc”.
So, there are 2+4+4+2+3+4+1+2+2=24 subsequences “abc” in total.

solution

/*
题意：
+ 给出一个长为n，只由a,b,c,?组成的字符串。将k个问号替换为a,b,c得到3^k种字符串。求这3^k种字符串中，有多少个子串abc。
思路：
+ 定义dp[i][0/1/2/3]表示前i个字符，序列,"a","ab","abc"的个数。然后用滚动数组优化为一维的。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 600000+10;
const int mod = 1e9+7;

LL f[10];

int main(){
	ios::sync_with_stdio(false);
	int n;  cin>>n;
	string s;  cin>>s;  s="0"+s;
	
	f[0] = 1;
	for(int i = 1; i <= n; i++){
		if(s[i]=='a')
			f[1] = (f[1]+f[0])%mod;
		else if(s[i]=='b')
			f[2] = (f[2]+f[1])%mod;
		else if(s[i]=='c')
			f[3] = (f[3]+f[2])%mod;
		else if(s[i]=='?'){
			f[3] = (3*f[3]%mod+f[2])%mod;
            f[2] = (3*f[2]%mod+f[1])%mod;
            f[1] = (3*f[1]%mod+f[0])%mod;
            f[0] = 3*f[0]%mod;
		}
	}
	cout<<f[3]<<"\n";
	return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/114069558