原题链接
题意：
给定一个含有abc?的字符串,?可能是abc中的任意一个,求所有可能的无?字符串中,子序列abc出现的次数.
思路：
dp[i][j]表示前i个字母里j子序列的个数，其中j== 1表示子序列a，j== 2表示子序列ab，j== 3表示子序列abc。
最后答案就是dp[n][3]。
再来看每一步的转移：
1.第i位是a,dp[i][1]=dp[i-1][1]+tmp;
假设前i位里?的个数为k，那么这个?有a,b,c三种可能，就会将原先的串变为3^k种串，每个串里在第i位上都是a，所以要算3 ^k次。tmp表示3 ^k,从头累加。
2.第i位是b，dp[i][2]=dp[i-1][2]+dp[i-1][1];
含义取到第i-1个位置时ab子序列的个数，再加上取到第i-1个位置时a子序列的个数，后者在第i位取b时也可以构成ab子序列。
3.第i位为c，dp[i][3]=dp[i-1][3]+dp[i-1][2];解释同2。
在上面三种情况时，其他非j情况的子序列都是直接累加前一个的，因为不会对他们产生影响。
4.第i位为？，考虑对每种序列的影响：
如果?放a的话，那么会多tmp个a
如果?放b的话，多dp[i-1][1]个ab
如果?放c的话，多dp[i-1][2]个abc
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } const int inf=0x3f3f3f3f; const ll mod=1e9+7; const ll INF = 0x3f3f3f3f3f3f3f3f; const int maxn=2e5+7,N=1e7+10; const double PI = atan(1.0)*4; const double eps=1e-6; char s[maxn]; ll dp[maxn][4]; int main() { int n; ll tmp=1; scanf("%d%s",&n,s+1); for(int i=1;i<=n;i++){ if(s[i]=='a'){ dp[i][1]=(dp[i-1][1]+tmp)%mod; dp[i][2]=(dp[i-1][2])%mod; dp[i][3]=(dp[i-1][3])%mod; } else if(s[i]=='b'){ dp[i][1]=(dp[i-1][1])%mod; dp[i][2]=(dp[i-1][2]+dp[i-1][1])%mod; dp[i][3]=(dp[i-1][3])%mod; } else if(s[i]=='c'){ dp[i][1]=(dp[i-1][1])%mod; dp[i][2]=(dp[i-1][2])%mod; dp[i][3]=(dp[i-1][3]+dp[i-1][2])%mod; } else if(s[i]=='?'){ dp[i][1]=(dp[i-1][1]*3+tmp)%mod; dp[i][2]=(dp[i-1][2]*3+dp[i-1][1])%mod; dp[i][3]=(dp[i-1][3]*3+dp[i-1][2])%mod; tmp=tmp*3%mod; } } out(dp[n][3]); return 0; }
![洛谷P1216-[USACO1.5][IOI1994]数字三角形 Number Triangles（DP）](https://ucc.alicdn.com/images/user-upload-01/20200726134345890.png?x-oss-process=image/resize,h_160,m_lfit)
