衡阳网站建设网站,科技布沙发优缺点,兰州网站建设哪家公司好,用asp做的网站打开页面很慢传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个长度为nnn的串#xff0c;包含a,b,c,?a,b,c,?a,b,c,?四种字符#xff0c;其中???可以变成为a,b,ca,b,ca,b,c的任意一种#xff0c;让你求abcabcabc子序列出现的次数。
思路#xff1a;
…传送门
文章目录题意思路题意
给你一个长度为nnn的串包含a,b,c,?a,b,c,?a,b,c,?四种字符其中???可以变成为a,b,ca,b,ca,b,c的任意一种让你求abcabcabc子序列出现的次数。
思路
考虑如果有xxx个问号那么当前这个串就被分成了3x3^x3x个串串。设dp[i][j]dp[i][j]dp[i][j]表示到了第iii位状态为jjj的串出现了多少次j0j0j0表示aaaj1j1j1表示abababj2j2j2表示abcabcabc。先给出转移方程 当s[i]!′?′s[i]!?s[i]!′?′时f[i][0]f[i−1][0]3cnti−1f[i][0]f[i-1][0]3^{cnt_{i-1}}f[i][0]f[i−1][0]3cnti−1f[i][1]f[i−1][1]f[i−1][0]f[i][1]f[i-1][1]f[i-1][0]f[i][1]f[i−1][1]f[i−1][0]f[i][2]f[i−1][2]f[i−1][1]f[i][2]f[i-1][2]f[i-1][1]f[i][2]f[i−1][2]f[i−1][1] 当s[i]′?′s[i]?s[i]′?′时f[i][0]f[i−1][0]∗33cnti−1f[i][0]f[i-1][0]*33^{cnt_{i-1}}f[i][0]f[i−1][0]∗33cnti−1f[i][1]f[i−1][1]∗3f[i−1][0]f[i][1]f[i-1][1]*3f[i-1][0]f[i][1]f[i−1][1]∗3f[i−1][0]f[i][2]f[i−1][2]∗3f[i−1][1]f[i][2]f[i-1][2]*3f[i-1][1]f[i][2]f[i−1][2]∗3f[i−1][1] 其中cnticnt_icnti表示到了第iii位???出现的次数。 这里解释一下由于???会产生3cnti−13^{cnt_{i-1}}3cnti−1个aaa所以需要加上3cnti−13^{cnt_{i-1}}3cnti−1个aaa。 在???处会分成三个部分所以要乘上333。
// Problem: F. Number of Subsequences
// Contest: Codeforces - Codeforces Round #674 (Div. 3)
// URL: https://codeforces.com/contest/1426/problem/F
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
char s[N];
LL f[N][4];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int y; int x;scanf(%d%s,n,s1);LL add1;for(int i1;in;i) {for(int j0;j3;j) f[i][j]f[i-1][j];if(s[i]!?) {if(s[i]a) f[i][0]add;if(s[i]b) f[i][1]f[i-1][0];if(s[i]c) f[i][2]f[i-1][1];} else {f[i][0]f[i-1][0]*3%modadd;f[i][1]f[i-1][1]*3%modf[i-1][0];f[i][2]f[i-1][2]*3%modf[i-1][1];addadd*3%mod;}for(int j0;j3;j) f[i][j]%mod;}printf(%lld\n,f[n][2]%mod);return 0;
}
/**/
