Submission #3024374

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <string>
#define SIZE 100005
#define INF 1000000005LL
#define MOD 1000000007

#include<iostream>

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll dpA[SIZE],dpB[SIZE],dpC[SIZE],dp[SIZE];

int main()
{
	string S;
	cin >> S;
	const int n = S.size();
	dp[0] = 1;
	dpA[0]=dpB[0]=dpC[0]=0;
	for(int i=0;i<n;i++){
		if(S[i] == 'A'){
			dpA[i+1] = dpA[i] + dp[i];
			dpB[i+1] = dpB[i];
			dpC[i+1] = dpC[i];
			dp[i+1] = dp[i];
		}else if(S[i] == 'B'){
			dpA[i+1] = dpA[i];
			dpB[i+1] = dpB[i] + dpA[i];
			dpC[i+1] = dpC[i];
			dp[i+1] = dp[i];
		}else if(S[i] == 'C'){
			dpA[i+1] = dpA[i];
			dpB[i+1] = dpB[i];
			dpC[i+1] = dpC[i] + dpB[i];
			dp[i+1] = dp[i];
		}else if(S[i] == '?'){
			dpA[i+1] = dpA[i]*3 + dp[i];
			dpB[i+1] = dpB[i]*3 + dpA[i];
			dpC[i+1] = dpC[i]*3 + dpB[i];
			dp[i+1] = dp[i]*3;
		}
		dpA[i+1] %= MOD;
		dpB[i+1] %= MOD;
		dpC[i+1] %= MOD;
		dp[i+1] %= MOD;
	}
	cout << dpC[n] << endl;
	return 0;
}

Submission Info

Judge Result