codeforces1426F Number of Subsequences

Number of Subsequences"/>

codeforces1426F Number of Subsequences

求abc子序列的个数，那么我们只要枚举每一个b的位置，然后求前缀所有情况a的数量之和，和后缀所有情况c的数量之和，把他们乘起来，就是这里取b对答案总的贡献了

prea表示前缀所有情况a数量之和，prenum表示前缀所有情况数量

如果s[i]='a'，那么说明prenum是不变的，但是每一种情况下的前缀都会多一个a，所以总共多prenum[i]个a

如果s[i]='?'，那么这里选abc都行，prenum就*3,等于选b,c时，都是prea[i-1]个a，选a时，就是prea[i-1]+prenum[i-1]个a，加起来就行

sufc同理

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxl=3e5+10;
const int mod=1e9+7;int n,m,cnt,tot,cas;ll ans;
int a[maxl];
ll prea[maxl],prenum[maxl],sufc[maxl],sufnum[maxl];
bool vis[maxl];
char s[maxl];inline void prework()
{scanf("%d",&n);scanf("%s",s+1);
}inline void upd(ll &x,ll y)
{x=(x+y)%mod;
}inline void mainwork()
{prenum[0]=1;for(int i=1;i<=n;i++)if(s[i]=='a'){	upd(prea[i],prea[i-1]+prenum[i-1]);prenum[i]=prenum[i-1];}else if(s[i]=='?'){upd(prenum[i],prenum[i-1]*3);upd(prea[i],prea[i-1]*2);upd(prea[i],prea[i-1]+prenum[i-1]);}elseprea[i]=prea[i-1],prenum[i]=prenum[i-1];sufnum[n+1]=1;for(int i=n;i>=1;i--)if(s[i]=='c'){upd(sufc[i],sufc[i+1]+sufnum[i+1]);sufnum[i]=sufnum[i+1];}else if(s[i]=='?'){upd(sufnum[i],sufnum[i+1]*3);upd(sufc[i],sufc[i+1]*2);upd(sufc[i],sufc[i+1]+sufnum[i+1]);}elsesufc[i]=sufc[i+1],sufnum[i]=sufnum[i+1];for(int i=1;i<=n;i++)if(s[i]=='b' || s[i]=='?')upd(ans,prea[i-1]*sufc[i+1]);
}inline void print()
{printf("%lld\n",ans);
}int main()
{int t=1;//scanf("%d",&t);for(cas=1;cas<=t;cas++){prework();mainwork();print();}return 0;
}