HDU 7131 Nun Heh Heh Aaaaaaaaaaa

发表于 | 分类于 | 评论数：

摘要

求给出的字符串 $S$ 中 nunhehhehaaa... 子序列的个数

恶臭题目；随意DP一下

题面

题解

计数DP？

直接的想法就是统计每个位置左侧 nunhehheh 的个数和右侧 a 的个数。

但是要避免算重，对串nunhehhehaaa...定位一下，约定在第一个 a 处计数。

如何统计左侧 nunhehheh 个数？DP，$F[i][k]$ 表示 $S[1\cdots i]$ 包含多少个目标串的 $k$ 长前缀

$F[i][k]=F[i-1][k]+[S[i]==Aim[k]]*F[i-1][k-1]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//https://acm.dingbacode.com/showproblem.php?pid=7131
//2021-10-13 nksbwen

#include <cstdio>
#include <cstring>

const int MAXL=100111;
const int MOD=998244353;

int sum(const int &a, const int &b){
	return a+b-((a+b>=MOD)?MOD:0);
}

int mul(const int &a, const int &b){
	return 1LL*a*b%MOD;
}

int pow(int a, int k){
	int r=1;
	while(k){
		if(k&1)	r=mul(r, a);
		a=mul(a, a);k>>=1;
	}
	return r;
}

int T;
char Aim[10]="nunhehheh";
char input[MAXL];
int len;

int CntA[MAXL];
int DP[MAXL][10];

int main(){
	
	scanf("%d", &T);
	
	while(T--){
		scanf("%s", input);
		len=strlen(input);
		for(int i=0;i<=len;++i)	for(int j=0;j<10;++j)	DP[i][j]=0;
		DP[0][0]=1;
		for(int i=0;i<len;++i){
			for(int j=0;j<=9;++j){
				DP[i+1][j]=sum(DP[i][j], DP[i+1][j]);
				if(Aim[j]==input[i]){
					DP[i+1][j+1]=sum(DP[i][j], DP[i+1][j+1]);
				}
			}
		}
		CntA[len]=0;
		for(int i=len;i>0;--i)	CntA[i-1]=CntA[i]+(input[i-1]=='a');
		int Ans=0;
		for(int i=0;i<len;++i){
			if(CntA[i]!=CntA[i+1]){
				Ans=sum(Ans, mul(DP[i][9], pow(2, CntA[i+1])));
				// printf("%d %d %d \n", i, DP[i][9], CntA[i+1]);
			}
		}
		printf("%d\n", Ans);
	}
	
	return 0;
}