UOJ Logo Universal Online Judge

UOJ

#429. 【集训队作业2018】串串划分

统计

给你一个长度为 $n$ 的字符串 $S$,你需要将其划分成若干个不相交的非空连续子串 $s_1,s_2, ... , s_k(k \ge 1)$,满足:

  • 每个子串 $s_i(1 \le i \le k)$ 是不循环的。
  • 相邻的两个子串不同。即 $s_i \neq s_{i+1} (1\le i \lt k)$。
  • $s_1,s_2, ... ,s_k$从左到右拼接起来恰好为原串。即$S=\overline{s_1s_2...s_k}$。

一个字符串 $S$ 是循环的,当且仅当存在一个整数 $k(k \ge 2)$ 和一个字符串 $s$,使得 $k$ 个 $s$ 拼接起来后的字符串与 $S$ 相等。例如字符串 $S=\text{abab}$ 是循环的,因为存在 $k=2,s=\text{ab}$。一个字符串是不循环的,当且仅当它不是循环的。字符串 $\text{ababa}$ 和 $\text{abcac}$ 就是不循环的。

你需要计算有多少种不同的划分方法。由于方案数可能很大,你只需要输出方案数模 $998244353$ 的值。两个划分方法不同是指划分出的子串序列不同。

输入格式

输入只有一行,包含一个只由小写字母组成的字符串 $S$。

输出格式

输出一个整数,表示方案数模 $998244353$ 的值。

样例一

input

ababab

output

22

样例二

input

abracadabracadabracadabra

output

16762880

限制与约定

对于所有数据,有$|S| \le 200000$。

  • 子任务 $1$($7\%$):$|S| \le 300$。
  • 子任务 $2$($10\%$):$|S| \le 2000$。
  • 子任务 $3$($13\%$):$|S| \le 8000$。
  • 子任务 $4$($5\%$):$S$ 的每个字符从指定的某个字符集中随机生成。
  • 子任务 $5$($25\%$):保证对于 $S$ 的任意子串,要么它是不循环的,要么它的循环次数(即题面描述中的 $k$)不会超过 $10$。
  • 子任务 $6$($40\%$):无特殊限制。

时间限制:$1\mathtt{s}$

空间限制:$512\mathtt{MB}$

下载

样例数据下载