题目
CF1426F Number of Subsequences
题解
从左往右扫描,记录一些前缀(a,a?,?b,??,?,ab)的数量,同时计算答案。记所有”?”的数量为k,sum[1/2/3/4/5/6]分别表示前缀a/a?/?b/??/?/ab的数量。
代码
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 |
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+5; const ll MOD=1e9+7; int n; ll k,ans,sum[8]; char s[maxn]; inline ll mul(ll a,ll b) { if(b<0) return 0; ll ans=1; for( ;b;b>>=1) { if(b&1) ans=ans*a%MOD; a=a*a%MOD; } return ans; } int main() { scanf("%d%s",&n,s+1); for(int i=1;i<=n;i++) if(s[i]=='?') k++; for(int i=1;i<=n;i++) { if(s[i]=='a') sum[1]=(sum[1]+1)%MOD; else if(s[i]=='b') { sum[6]=(sum[6]+sum[1])%MOD; sum[3]=(sum[3]+sum[5])%MOD; } else if(s[i]=='c') ans=(ans+sum[6]*mul(3,k)%MOD+(sum[2]+sum[3])*mul(3,k-1)%MOD+sum[4]*mul(3,k-2)%MOD)%MOD; else { ans=(ans+sum[6]*mul(3,k-1)%MOD+(sum[2]+sum[3])*mul(3,k-2)%MOD+sum[4]*mul(3,k-3)%MOD)%MOD; sum[4]=(sum[4]+sum[5])%MOD; sum[2]=(sum[2]+sum[1])%MOD; sum[5]=(sum[5]+1)%MOD; } } printf("%lld\n",ans); return 0; } |
【小白解析】
此题动用极其活跃的动态分配思路;本质上并不复杂,关键在于理解每一步状态转移的意义。值得一提的是,该算法需要构造mul(a,b),即喜闻乐见的快速幂,来提高long long类型幂的运算速度。
援引博主的设定:
即:
由此从27行开始,对每一个状态转移展开讲解:
若读取到a,现有的a数量加1;
若读取到b,ab的数量在a当前的数量上加1(此操作从s[1]开始向后遍历至i,不会影响到i以后的字符,故此时的sum[1]即为b之前所有a的总和),同时?b的数量在当前?的数量上加1。
若读取到c,进行一次结算:
读取到?的情况与c类似——将该?作为c看待,即可重复对c的操作(但相应操作中,每个k需要优先-1,因为已预先牺牲了这个读取到的“?”)。38至40行则分别更新??,a?与?的情况。
最后输出ans即为所要求的结果。