Codeforces1426 F.Number of Subsequences（枚举，组合数学推式子）

题意：

给定一个只包含“abc?”的字符串，其中’?'可以替换为abc的任意一种。 问对于所有可能的串，子序列abc的总和是多少。 答案对1e9+7取模。

数据范围：n<=2e5

解法：

$三元组统计的套路：枚举中间的b，统计两端的a和c计算贡献。$

$假设左边有x{个}^{\prime }{a}^{\prime }，y{个}^{\prime }{?}^{\prime }。$

$假设i个变成a，那么y-i个就变成b/c，方案数为C(y,i)\ast 2^{y-i}$

$加上固定的x个,那么可能的a的个数总为:{\sum }_{i=0}^{y}C(y,i)\ast 2^{y-i}\ast (x+i)$

$将式子拆开变为:$

${\sum }_{i=0}^{y}C(y,i)\ast 2^{y-i}\ast i+{\sum }_{i=0}^{y}C(y,i)\ast 2^{y-i}\ast x$

$={\sum }_{i=0}^{y}C(y,i)\ast 2^{y-i}\ast i+(1+2{)}^y\ast x$

$={\sum }_{i=0}^{y}C(y,i)\ast 2^{y-i}\ast i+3^y\ast x$

$因为C(n,m)=\frac{n!}{m!\ast (n-m)!},因此式子变为$

${\sum }_{i=0}^y\frac{y!}{i!\ast (y-i)!}\ast 2^{y-i}\ast i+3^y\ast x$

$={\sum }_{i=0}^y\frac{y!}{(i-1)!\ast (y-i)!}\ast 2^{y-i}+3^y\ast x$

$=y\ast {\sum }_{i=0}^y\frac{(y-1)!}{(i-1)!\ast (y-i)!}\ast 2^{y-i}+3^y\ast x$

$=y\ast {\sum }_{i=0}^y\frac{(y-1)!}{(i-1)!\ast (y-i)!}\ast 2^{y-i}+3^y\ast x$

$=y\ast {\sum }_{i=0}^{y}C(y-1,y-i)\ast 2^{y-i}+3^y\ast x$

$=y\ast {\sum }_{i=0}^{y}C(y-1,y-i)\ast 2^{y-i}+3^y\ast x$

$左边当i=0时=0,那么下标可以改为从i=1开始$

$=y\ast {\sum }_{i=1}^{y}C(y-1,y-i)\ast 2^{y-i}+3^y\ast x$

$y-i可以替换为i,因为是对称的$

$=y\ast {\sum }_{i=0}^{y-1}C(y-1,i)\ast 2^i+3^y\ast x$

$=y\ast (2+1{)}^{y-1}+3^y\ast x$

$=3^{y-1}\ast y+3^y\ast x$

$预处理pow(3)即可$

$上面计算的是左边的数量,右边一样的$

$参考：https://www.luogu.com.cn/blog/ZigZagKmp/CF1426F-solution$

code：

#include<bits/stdc++.h> using namespace std; #define int long long const int maxm=2e5+5; const int mod=1e9+7; char s[maxm]; int p3[maxm]; int lx[maxm],rx[maxm]; int ly[maxm],ry[maxm]; int n; void init(){ p3[0]=1; for(int i=1;i<maxm;i++)p3[i]=1ll*p3[i-1]*3%mod; } signed main(){ init(); cin>>n; scanf("%s",s+1); for(int i=1;i<=n;i++){ lx[i]=lx[i-1]; ly[i]=ly[i-1]; if(s[i]=='a')lx[i]++; else if(s[i]=='?')ly[i]++; } for(int i=n;i>=1;i--){ rx[i]=rx[i+1]; ry[i]=ry[i+1]; if(s[i]=='c')rx[i]++; else if(s[i]=='?')ry[i]++; } int ans=0; for(int i=1;i<=n;i++){ if(s[i]=='b'||s[i]=='?'){ int L=0; L+=p3[ly[i-1]]*lx[i-1]%mod; if(ly[i-1])L+=p3[ly[i-1]-1]*ly[i-1]%mod; int R=0; R+=p3[ry[i+1]]*rx[i+1]%mod; if(ry[i+1])R+=p3[ry[i+1]-1]*ry[i+1]%mod; ans=(ans+L*R)%mod; } } cout<<ans<<endl; return 0; }

---