【牛客练习赛50】tokitsukaze and Segmentation

题目描述

tokitsukaze有一个长度为 $n$n的字符串，字符串仅包含 ${\prime }^{}{0}^{\prime }{-}^{\prime }{9}^{\prime }$′0′−′9′。
tokitsukaze要把这个字符串切割成若干个子串，每个子串作为一个十进制的数，能被3整除，且不含前导0。
问有多少种切割的方案。由于答案可能很大，请输出mod $998244353$998244353 后的结果。

输入描述:

第一行包含一个正整数 $n$n,( $1\le n\le 10^5$1≤n≤105)。
第二行包含一个长度为 $n$n的字符串 $s$s,( ${\prime }^{}{0}^{\prime }\le s\left[i\right]{\le }^{\prime }{9}^{\prime }$′0′≤s[i]≤′9′)。

输出描述:

输出一个整数，表示方案数，mod $998244353$998244353 后的结果。

示例1

输入

1
1

输出

0

示例2

输入

1
0

输出

1

示例3

输入

4
1203

输出

3

说明
(1) 1203
(2) 120|3
(3) 12|0|3
所以方案数为3。
注意：12|03，视作不合法，因为有前导0。

Solution

易知:如果 $3\mid s$3∣s, $3\mid t$3∣t, 那么 $3\mid s\ast 10^x+t$3∣s∗10x+t $x$x为 $t$t的位数
所以分段递推。
分成x段，保证每段是3的倍数且最短
用v记录是否为0

for i = 1 to n do
	t = t + a[i]
	tmp = (tmp + a[i] - '0') % 3
	if tmp == 0 //找到了
	    if t == '0' v.push_back(true)
	    else v.push_back(false)
	    t = '0'

特判无解：

if v.empty or tmp != 0
	puts("0");
	exit

初始化 $f[x+1]=1$f[x+1]=1
伪代码:

for i = x downto 1
    if 第i个=0
    	f[i] = f[i + 1]
    else
        f[i] = (f[i + 1] + f[i + 2] + ... f[x + 1]) % Mod

代码如下

#include <cstdio>
#include <vector>
#include <string>

using namespace std;

const long long N = 1e5 + 10, Mod = 998244353;
long long n, tmp = 0, f[N];
char a[N];
string t("");

vector<bool> v;

long long main()
{
	scanf("%lld%s", &n, a + 1);
	for (long long i = 1; i <= n; i++)
	{
		t += a[i];
		tmp = (tmp + a[i] - '0') % 3;
		if (tmp == 0)
		{
			if (t == "0") v.push_back(true);
			else v.push_back(false);
			t = "";
		}
	}
	if (v.empty() || tmp != 0)
	{
		puts("0");
		return 0;
	}
	tmp = 1; f[v.size()] = 1;
	for (long long i = v.size() - 1; i >= 0; i--)
	{
		if (v[i])
			f[i] = f[i + 1];
		else f[i] = tmp;
		tmp = (tmp + f[i]) % Mod;
	}
	printf("%lld\n", f[0]);

	return 0;
}