← 返回题目列表

AtCoder · agc020_e

E. 编码子集

中文机器翻译题面 查看原题

分数: 1400 点

问题陈述

考虑以下一组规则来对由以下内容组成的字符串进行编码 0 和 1:

  • 字符串 0 和 1 可以编码为 0 和 1。
  • 如果字符串 A 和 B 可以编码为 P 和 Q分别,然后字符串 AB 可以编码为 PQ.
  • 如果字符串 A 可以编码为 P 和 K \geq 2 是正整数,则字符串 AA...A (A 重复 K 次)可以编码为 (PxK).

例如,字符串 001001001除其他可能性外,可以编码为 001001001, 00(1(0x2)x2)1 和 (001x3).

让我们调用字符串 A 字符串的子集 B 如果:

  • A 和 B 长度相等并且由以下组成 0 和 1;
  • 对于所有指数 i 这样 A_i = 1,这也是事实 B_i = 1.

给你字符串 S 组成 0 和 1。找到所有子集的不同编码的总数 S,模数 998244353.

约束

  • 1 \leq |S| \leq 100
  • S 包括 0 和 1.

输入

输入由标准输入按以下格式给出:

S

输出

打印所有子集的不同编码总数 S 模数 998244353.


示例输入 1

011

示例输出 1

9

有四个子集 S:

  • 011 可以编码为 011 和 0(1x2);
  • 010 可以编码为 010;
  • 001 可以编码为 001 和 (0x2)1;
  • 000 可以编码为 000, 0(0x2), (0x2)0 和 (0x3).

因此,所有子集的编码总数 S is 2 + 1 + 2 + 4 = 9.


示例输入 2

0000

示例输出 2

10

这次 S 只有一个子集,但可以编码为 10 不同的方式。


示例输入 3

101110

示例输出 3

156

示例输入 4

001110111010110001100000100111

示例输出 4

363383189

不要忘记对结果取模 998244353.