NOIPアナログ試合コード

タイトルの説明

1文字列strのp型符号化aの定義は、strをb 1個のc 1,b 2個のc 2...bn個のcnとして表し、その後、b 1,c 1,b 2,c 2,...,bn,cnの終端をつなぎ合わせた文字列の中で最も短い文字列をaとする.例えば、文字列12234411は、「1つの1、2つの2、1つの3、2つの4、3つの1」と記述することができ、従って、12234411のp型符号化は112132431であると述べた.
同様の理屈では、0000000000は「11個の0」と記述できるため、p型の符号化は110である.100200300は、「1つの1、2つの0、1つの2、2つの0、1つの3、2つの0」と記述することができ、したがって、そのp型符号化は11201、2201320である.
明らかに、1つの列strのp型符号化は固定されているが、複数の列のp型符号化が同じである可能性がある.現在、bx 2 kは文字列strのp型符号化aを得たが、彼は元の文字列が何なのか分からない.彼は今、どのような文字列のp型符号化がaなのか知りたいと思っている.bx 2 kはdoubiで、彼はツンデレのあなたに教えてもらいに来ました.
入力
最初の行には、文字列aを表す文字列が含まれます.
しゅつりょく
最初の行には、strの数を998244353の余剰数で割った正の整数が含まれます.
サンプル入力
1415
サンプル出力
2
問題解
dp[i]dp[i]dp[i]は、入力文字列においてiを末尾とする文字列接頭辞に対応する文字列数を表すことを考慮する.言い換えれば、どのくらいの文字列があるかを示すp型符号化は、その入力文字列のうち位置が(1~i)のサブ列である.少なくとも2人は新しいサブストリングを構成することができるので,d p[i]dp[i]dp[i]dp[i]=Σk=2 isum_{k=2}^iΣk=2 i d p[i−k]dp[i−k]dp[i−k]dp[i−k]dp[i−k]を接頭辞と最適化で用い,s u m[i]sum[i]sum[i]sum[i]sum[i]はΣk=1 isum_を表す{k=1}^iΣk=1 i 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]sum[i−2]であるが、そう簡単ではない場合がある.d p[i]dp[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−k]dp[i−k]dp[i−k]dp[i−k]dp[i−k]dp[i−k]dp[i−k]によってd p[i]sum 2[i]sum 2[i]sum 2[i]は、iの前に0の干渉が存在するため、d p[i]dp[i]dp[i]dp[i]dp[j]dp[j]dp[j]の和また,aが11111の場合,上記の方法で行うと3が得られるが,実際の答えは1であることが分かった.なぜなら,我々のやり方では,「1個1,11個1」という案があり,この案は不合理であり,12個1に統合する必要があるからである.そのため、私たちはこの問題を解決しなければなりません.d p[i]dp[i]dp[i]dp[i]を求めると、iの前でa[i]a[i]a[i]と等しい位置jに対応するdp[j]はd p[i]dp[i]dp[i]に移行できないことが分かった.現在位置の2つの以前のa[i]と等しい位置jに対応するd p[j]dp[j]dp[j]dp[j]の和をs u m 3[i]dp[i]dp[i]dp[i]=s u m[i−2]sum[i−2]−s u m 2[i−2]sum 2[i−2]sum 2[i−2]sum 2[i−2]−s u m 2[i]dp[i]sum 3[a[i]sum 3[a[i]とする.境界の場合、dp[0]dp[0]dp[0]==1、dp[1]dp[1]=0;
注意点:
1.減算後の型抜きに注意する.aの長さが1、またはaの1位が0の場合は特判が必要で、0を出力する
コードは次のとおりです.

#include 
#include 
#include 
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
");
		return 0;
	}
	if(len == 1){
		printf("0
");
		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
", dp[len]);
	return 0;
}