题目描述

一个字符串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[i−k],用一下前缀和优化， 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[i−2]，然而有些情况没有这么简单。当求到 d p [ i ] dp[i] dp[i]时, a [ i − k + 1 ] a[i - k + 1] a[i−k+1]为0，则 d p [ i ] dp[i] dp[i]不能由 d p [ i − k ] dp[i - k] dp[i−k]，因此我们再设 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[i−2] - s u m 2 [ i − 2 ] sum2[i - 2] sum2[i−2] - 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;
}