【Abc104-D】We Love ABC

Source and Judge

Arc100-D

Problem

【Description】
给出一个字符串,只有A,B,C和通配符?
答案为:枚举出各种情况,每种情况,不同位置三元组满足(A,B,C),其数量之和
【Input】
字符串s
【Output】
输出和,模1e9+7
【Limited conditions】
|s|<=10^5
【Sample input 1】
A??C
【Sample output 1】
8
【Sample input 2】
ABCBC
【Sample output 2】
3
【Sample input 3】
????C?????B??????A???????
【Sample output 3】
979596887
【Sample explanation】

Record

30min
刚长途旅游完
只有abc

Analysis

请先思考后再展开

第一次想出D
因为同样的三元组,可能会多次统计
直接枚举每个b和?,考虑其贡献即可

Code

请先思考后再展开
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
const ll MOD=1e9+7;
char s[MAXN];
ll a[MAXN],c[MAXN],wen[MAXN];
ll three[MAXN];
int main()
{
three[0]=1;for(int i=1;i<MAXN;i++) three[i]=(three[i-1]*3)%MOD;
scanf("%s",s+1);
int len=strlen(s+1);
for(int i=1;i<=len;i++)
{
a[i]=a[i-1]+(s[i]=='A');
c[i]=c[i-1]+(s[i]=='C');
wen[i]=wen[i-1]+(s[i]=='?');
}
ll ans=0;
for(int i=1;i<=len;i++)
if(s[i]=='B')
{
ans+=a[i-1]*(c[len]-c[i])%MOD*three[wen[len]]%MOD;ans%=MOD;//(a,b,c)
ans+=wen[i-1]*(c[len]-c[i])%MOD*three[wen[len]-1]%MOD;ans%=MOD;//(?,b,c)
ans+=a[i-1]*(wen[len]-wen[i])%MOD*three[wen[len]-1]%MOD;ans%=MOD;//(a,b,?)
ans+=wen[i-1]*(wen[len]-wen[i])%MOD*three[wen[len]-2]%MOD;ans%=MOD;//(?,b,?)
}
else if(s[i]=='?')
{
ans+=a[i-1]*(c[len]-c[i])%MOD*three[wen[len]-1]%MOD;ans%=MOD;//(a,?,c)
ans+=wen[i-1]*(c[len]-c[i])%MOD*three[wen[len]-2]%MOD;ans%=MOD;//(?,?,c)
ans+=a[i-1]*(wen[len]-wen[i])%MOD*three[wen[len]-2]%MOD;ans%=MOD;//(a,?,?)
ans+=wen[i-1]*(wen[len]-wen[i])%MOD*three[wen[len]-3]%MOD;ans%=MOD;//(?,?,?)
}
printf("%lld",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/f88a.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%