考虑下面一个 $\texttt 0/\texttt 1$ 串的编码方式：
字符串 $\texttt 0, \texttt 1$ 分别可以被编码为 $\texttt 0, \texttt 1$。
若字符串 $A, B$ 分别可以被编码为 $P, Q$，则串 $A B$ 可以被编码为 $P Q$。
若字符串 $A$ 可以被编码为 $P$，则字符串 $A^K$ 可以被编码为 $\texttt{(} \cdot P \cdot \texttt{x} \cdot K \cdot \texttt{)}$，其中 $\cdot$ 表示字符串的连接，幂次表示循环串。
比如，$\texttt 0/\texttt 1$ 串 $\texttt{001001001}$ 可以被编码为如下三个串：$\texttt{001001001}, \texttt{00(1(0x2)x2)1}$ 以及 $\texttt{(001x3)}$。
称 $\texttt 0/\texttt 1$ 串 $A$ 是 $\texttt 0/\texttt 1$ 串 $B$ 的子集，如果：
$\left| A \right| = \left| B \right|$。
串 $A$ 中的每一位不大于串 $B$ 的对应位 (定义 $\texttt 0 < \texttt 1$)。
现在，给定一个 $\texttt 0/\texttt 1$ 串 $S$，你需要求出，对于所有是 $S$ 的子集的串 $T$，它的不同编码方案数之和。
共一行，包含一个 $\texttt 0/\texttt 1$ 串 $S$ ($1 \leq \left| S \right| \leq 100$)，表示题目给定的 $\texttt 0/\texttt 1$ 串。
输出一行一个整数，表示 $S$ 的所有自己的编码方案数之和模 $998244353$ 的值。
考虑 (类似) 区间 DP，即用 $f_S$ 表示对于 $S$ 的所有子串的答案。
我们根据 $S_1$ 是否被 "压缩" 分为两类：
$S_1$ 不压缩。
于是，我们将问题转化为了 $S \left[ 2 .. \left| S \right| \right]$ 的一个子问题。
而根据 $S_1 = \texttt 0$ 还是 $\texttt 1$ 决定了它有一个子集还是两个子集。
从而，有 $f_S \gets_+ \left( 1 + \left[ S_1 = 1 \right] \right) \cdot f_{S \left[ 2 .. \left| S \right| \right]}$。
$S_1$ 压缩。
设 $S_1$ 所在的段长度为 $i$，共压缩了 $j$ 段，从而对于满足条件的串 $T \subseteq S$，有 $T \left[ 1 .. i \right] = T \left[ i + 1 .. 2 i \right] = \cdots = T \left[ \left( j - 1 \right) \cdot i + 1 .. j \cdot i \right]$。
故 $T \subseteq S \left[ 1 .. i \right] \cap S \left[ i + 1 .. 2 i \right] \cap \cdots \cap S \left[ \left( j - 1 \right) \cdot i + 1 .. j \cdot i \right]$。
于是，整个问题就被分解为了两个子问题：$S \left[ 1 .. i \right] \cap S \left[ i + 1 .. 2 i \right] \cap \cdots \cap S \left[ \left( j - 1 \right) \cdot i + 1 .. j \cdot i \right]$ 及其子集的编码方案数，以及 $S \left[ j \cdot i + 1 .. n \right]$ 的编码方案数。
又这两部分的独立的，因此只需将这两部分的方案数直接乘起来即可。
于是，这一部分的转移为 $$ f_S \gets_+ \sum_{1 \leq i; 2 \leq j; i \cdot j \leq \left| S \right|} f_{S \left[ 1 .. i \right] \cap S \left[ i + 1 .. 2 i \right] \cap \cdots \cap S \left[ \left( j - 1 \right) \cdot i + 1 .. j \cdot i \right]} \cdot f_{S \left[ j \cdot i + 1 .. n \right]} $$
综上，有 $$ \large \color {fuchsia} {f_S = \left( 1 + \left[ S_1 = 1 \right] \right) \cdot f_{S \left[ 2 .. \left| S \right| \right]} + \sum_{1 \leq i; 2 \leq j; i \cdot j \leq \left| S \right|} f_{S \left[ 1 .. i \right] \cap S \left[ i + 1 .. 2 i \right] \cap \cdots \cap S \left[ \left( j - 1 \right) \cdot i + 1 .. j \cdot i \right]} \cdot f_{S \left[ j \cdot i + 1 .. n \right]}} $$
具体实现的时候，可以使用 $128$ 位整数或 bitset 来存储。
如果暴力计算，那么复杂度将会是 $O \left( 2^\left| S \right| \right)$ 的，这无法接受。于是，我们尝试将其换成记忆化搜索，然后发现它过了。
这是为什么呢？我们来稍加精细分析地分析一波状态数。
首先，由单调性，不妨假设 $\left| S \right| = n = 100$。
考虑长度不超过 $\left \lfloor \dfrac n8 \right \rfloor = 12$ 的所有串，这样的串不超过 $2^{n/8} = 2^{12} = 4096$ 个。
考虑长度至少为 $\left \lceil \dfrac n8 \right \rceil = 13$ 的串，它一定可以通过如下方式得到：
取子串 → 缩小 (即求若干连续段的交) → 取子串 → 缩小 → 取子串。
且，"缩小" 的操作次数不超过 $2$ (因为每次缩小后，字符串长度至多为原串的一半)，且当缩小次数为 $2$ 时缩放因子 (即转移中的 $j$) 必须为 $2$ 或 $3$。
考虑缩放因子序列，如果长度为 $2$ (缩小次数为 $2$)，则有三种情形：
$\left[ 2, 2 \right]$。
第一次缩小相当于取相邻两个子串的交，然后取子串相当于不相邻两个子串的交，再缩小、取子串相当于四个子串的交。
这四个子串可以通过 (长度 $l$，第一个串起始点 $s_1$，第二个串起始点 $s_2$，第三个串起始点 $s_3$) 唯一决定。(注意 $s_4 = -s_1 + s_2 + s_3$)。
通过数学计算可以得到，满足条件的串数为 $\dfrac 1 {144} n^4 + O \left( n^3 \right)$。
$\left[ 2, 3 \right]$。
一共得到六个子串，可以通过四元组 $\left( l, s_1, s_2, s_4 \right)$ 唯一决定 ($s_3 = - s_1 + 2 s_2, s_5 = - s_1 + s_2 + s_4, s_6 = - 2 s_1 + 2 s_2 + s_4$)。
类似地，满足条件的串数为 $\dfrac 1 {480} n^4 + O \left( n^3 \right)$。
$\left[ 3, 2 \right]$。
一共得到六个子串，可以通过四元组 $\left( l, s_1, s_2, s_3 \right)$ 唯一决定 ($s_4 = - s_1 + s_2 + s_3, s_5 = - s_1 + 2 s_3, s_6 = - 2 s_1 + s_2 + 2 s_3$)。
类似地，满足条件的串数为 $\dfrac 1 {720} n^4 + O \left( n^3 \right)$。
$\left[ \xi \right]$ ($2 \leq \xi \leq 7$)。
由共 $\xi + 1$ 个子串，由三元组 $\left( l, s_1, s_2 \right)$ 决定。
满足条件的串数为 $\dfrac 1 {6 \xi^2} n^3 + O \left( n^2 \right)$。
综上，长度至少为 $13$ 的不同串数不超过 $\color {red} {\dfrac 1 {96} {n^4} + O \left( n^3 \right)}$ 个，大约是 $10^6$ 个左右，于是确实是合理的。
事实上，这个界还是比较松的，实测出来不同串的总数不超过 $50000$ 个。
从而，整个问题的复杂度的一个松界是 $O \left( \left| S \right|^4 + 2^{\left| S \right|/8} \right)$，可以通过。
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long u64;
typedef unsigned __int128 u128;
struct _hash_ {
static std::hash <u64> H;
inline size_t operator () (const u128 x) const {return H(u64(x >> 64)) * 20030731ull + H(u64(x));}
};
typedef std::unordered_map <u128, int, _hash_> map;
const int mod = 998244353;
map f;
inline int lg2(u128 x) {u64 *p = (u64*)&x; return p[1] ? std::__lg(p[1]) + 64 : *p ? std::__lg(*p) : -1;}
int solve(u128 x) {
map::iterator it = f.find(x);
if (it != f.end()) return it->second;
int i, j, L = lg2(x), ret = (1 + ll(x & 1)) * solve(x >> 1) % mod;
for (i = 1; (j = 2 * i) <= L; ++i) {
u128 U = x, bit = (u128)1 << i, mask = bit - 1;
for (; j <= L; j += i)
U &= U >> i, ret = (ret + (ll)solve((U & mask) | bit) * solve(x >> j)) % mod;
}
return f.emplace(x, ret), ret;
}
int main() {
char s[128], *p = s; u128 n = 1;
for (scanf("%s", s); *p; ++p) n = n * 2 + (*p & 1);
f.emplace(1, 1);
printf("%d\n", solve(n));
return 0;
}
坑1：注意一下评测环境，有些环境可能不滋磁 __int128，需要使用 bitset 代替。同时，在使用 unordered_map 的时候对于某些奇怪的类型手写 Hash 类。
坑2：保存不同长度的串时可以通过在最高位加 $1$ 的方法解决。同时，"缩小" 部分继续递归的串的长度为 $i$，而不是 $j \cdot i$ 或其它。