【题解】CF1426F Number of Subsequences

题目

CF1426F Number of Subsequences

题解

从左往右扫描,记录一些前缀(a,a?,?b,??,?,ab)的数量,同时计算答案。记所有”?”的数量为k,sum[1/2/3/4/5/6]分别表示前缀a/a?/?b/??/?/ab的数量。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年10月17日 下午8:06

【小白解析】
此题动用极其活跃的动态分配思路;本质上并不复杂,关键在于理解每一步状态转移的意义。值得一提的是,该算法需要构造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,k2)%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,k1)%MOD+

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

sum[4]*mul(3,k3)%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即为所要求的结果。