【题解】CF1426F Number of Subsequences

【小白解析】
此题动用极其活跃的动态分配思路；本质上并不复杂，关键在于理解每一步状态转移的意义。值得一提的是，该算法需要构造mul(a,b)，即喜闻乐见的快速幂，来提高long long类型幂的运算速度。
援引博主的设定：

sum[1/2/3/4/5/6]分别表示前缀a/a?/?b/??/?/ab的数量

即：

• sum[1]<->a
• sum[2]<->a?
• sum[3]<->?b
• sum[4]<->??
• sum[5]<->?
• sum[6]<->ab

由此从27行开始，对每一个状态转移展开讲解：

27：if(s[i]==‘a’) sum[1]=(sum[1]+1)%MOD;

若读取到a,现有的a数量加1；

28： else if(s[i]==‘b’)

29： {

30： sum[6]=(sum[6]+sum[1])%MOD;

31： sum[3]=(sum[3]+sum[5])%MOD;

32： }

若读取到b，ab的数量在a当前的数量上加1（此操作从s[1]开始向后遍历至i，不会影响到i以后的字符，故此时的sum[1]即为b之前所有a的总和），同时?b的数量在当前？的数量上加1。

33：else if(s[i]==‘c’)

34： ans=(ans+sum[6]*mul(3,k)%MOD+

(sum[2]+sum[3])*mul(3,k1)%MOD+

sum[4]*mul(3,k–2)%MOD)%MOD;

若读取到c，进行一次结算：

• 先考察现在既有的ab数量sum[6]，均可以与c组成abc，故剩余的所有？可以为任何字符，即有3^k个组合（函数表现为mul(3,k)）；
• 再考察现有a?与?b的总数sum[2]+sum[3]，其中前者可以使?变成b，成为ab，后者可以使?变成a，成为ab，随后便可与c组合。此时需要牺牲一个？的位置满足abc的构成，故剩余可自由变换的?数量为k-1，故不同组合需乘以mul(3,k-1)==3^(k-1)；
• 最后考察??的总数sum[4]。??必须成为ab以与c组合，故允许自由变换的?共有k-2个，sum[4]乘以mul(3,k-2)==3^(k-2)；

35： else

36： {

37： 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;

38： sum[4]=(sum[4]+sum[5])%MOD;

39： sum[2]=(sum[2]+sum[1])%MOD;

40： sum[5]=(sum[5]+1)%MOD;

41： }

读取到?的情况与c类似——将该？作为c看待，即可重复对c的操作（但相应操作中，每个k需要优先-1，因为已预先牺牲了这个读取到的“?”）。38至40行则分别更新??，a?与？的情况。

最后输出ans即为所要求的结果。