NOIP模拟赛 编码

08/06 17:21
阅读数 35

题目描述

一个字符串str的p型编码a的定义如下:把str表示成b1个c1,b2个c2…bn个cn,然后将b1,c1,b2,c2,…,bn,cn收尾拼接成的字符串中最短的字符串设为a。例如:字符串122344111可被描述为"1个1、2个2、1个3、2个4、3个1",因此我们说122344111的p型编码为1122132431。

类似的道理,00000000000可描述为"11个0",因此它的p型编码为110;100200300可描述为"1个1、2个 0、1个2、2个0、1个3、2个0",因此它的p型编码为112012201320。

很显然,一个串str的p型编码是固定的,但是可能有多个串的p型编码相同。现在bx2k获得了一个字符串str的p型编码a,但他不知道原来的字符串是啥,他现在想知道有多少种字符串的p型编码为a。bx2k是个doubi,他来请教傲娇的你。

输入

第一行包含一个字符串,表示字符串a。

输出

第一行包含一个正整数,为str的数量除以998244353的余数。

样例输入

1415

样例输出

2

题解

我们考虑 d p [ i ] dp[i] dp[i]表示在输入字符串中以i为结尾的字符串前缀所对应的字符串数量。换言之,它表示有多少字符串的p型编码为该输入字符串中位置为(1~i)的子串。由于至少两位才能构成一段新的子串
所以容易想到 d p [ i ] dp[i] dp[i] = ∑ k = 2 i \sum_{k=2}^i k=2i d p [ i − k ] dp[i - k] dp[ik],用一下前缀和优化, s u m [ i ] sum[i] sum[i]表示 ∑ k = 1 i \sum_{k = 1}^i k=1i d p [ i ] dp[i] dp[i]
所以 d p [ i ] dp[i] dp[i] = s u m [ i − 2 ] sum[i - 2] sum[i2],然而有些情况没有这么简单。当求到 d p [ i ] dp[i] dp[i]时, a [ i − k + 1 ] a[i - k + 1] a[ik+1]为0,则 d p [ i ] dp[i] dp[i]不能由 d p [ i − k ] dp[i - k] dp[ik],因此我们再设 s u m 2 [ i ] sum2[i] sum2[i]表示在i之前因为存在0的干扰不能转移到 d p [ i ] dp[i] dp[i]所有 d p [ j ] dp[j] dp[j]之和。
还有我们发现当a为11111时,我们用上面的方法去做,会得到3,而实际答案为1,因为照我们的做法,
有一种方案为“1个1,11个1”,这种方案是不合理的,需要合并为12个1。因此,我们得解决这个问题。
我们发现当求到 d p [ i ] dp[i] dp[i]时,在i前面与 a [ i ] a[i] a[i]相等的位置j所对应的dp[j]不能转移到 d p [ i ] dp[i] dp[i].
我们用 s u m 3 [ i ] sum3[i] sum3[i]表示在当前位置的两个以前所有与a[i]相等的位置j所对应的 d p [ j ] dp[j] dp[j]之和,
至此, d p [ i ] dp[i] dp[i] = s u m [ i − 2 ] sum[i - 2] sum[i2] - s u m 2 [ i − 2 ] sum2[i - 2] sum2[i2] - s u m 3 [ a [ i ] ] sum3[a[i]] sum3[a[i]];
边界情况, d p [ 0 ] dp[0] dp[0] = = = 1, d p [ 1 ] dp[1] dp[1] = 0;







注意点:

1.注意减法后的取模
2.当a的长度为1,或a的第一位为0时需要特判,输出0

代码如下:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1000005;
const int P = 998244353;
long long dp[N];
long long sum1[N];
long long sum2[N];
char a[N];
long long sum3[10];
int main(){
	int i, len;
	scanf("%s", a + 1);
	len = strlen(a + 1);
	dp[0] = 1;
	sum1[0] = 1;
	if(a[1] == '0'){
		printf("0\n");
		return 0;
	}
	if(len == 1){
		printf("0\n");
		return 0;
	}
	dp[1] = 0;
	for(i = 2; i <= len; i++){
		dp[i] = ((sum1[i - 2] - sum2[i - 2] - sum3[a[i] - '0']) % P + P) % P;
		sum1[i - 1] = (sum1[i - 2] + dp[i - 1]) % P;
		if(a[i] == '0') sum2[i - 1] = (sum2[i - 2] + dp[i - 1]) % P;
		else {
			sum3[a[i - 1] - '0'] = (sum3[a[i - 1] - '0'] + dp[i - 1]) % P;
			sum2[i - 1] = sum2[i - 2];
		}
	}
	printf("%lld\n", dp[len]);
	return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部