【AtCoder Grand Contest 020 E】Encoding Subsets
状压，记忆化搜索。
题目大意：
考虑以下 01 串的编码方式：
- 字符串
0和1可以被编码为 $\texttt 0$ 和 $\texttt 1$。 - 字符串 $A,B$ 分别编码为 $P,Q$，则字符串 $AB$ 可以编码为 $PQ$。
- 若字符串 $A$ 编码为 $P$，则字符串 $AAA\cdots$（$k$ 个 $A$）可以编码为 $\texttt{(} \cdot P \cdot \texttt{x} \cdot k \cdot \texttt{)}$
例如字符串 001001001 可以编码为 $\texttt{001001001}$，$\texttt{00(1(0x2)x2)1}$ 或者 $\texttt{(001x3)}$ 等。
现在给出 01 串 $A$，求 $A$ 的所有子集的不同编码方案数之和。
定义 $B$ 是 $A$ 的子集，满足它们长度相等且把它们当成二进制数看时，$A$ 和 $B$ 按位与的结果等于 $B$，$A$ 和 $B$ 按位或的结果等于 $A$。
题解：
考虑状压 DP。令 $f_S$ 表示字符串 $S$ 及其子集的不同编码方案数之和。
考虑两种转移方式：
$S_1$ 独立为一个字符。这种情况我们只需要递归计算 $f_{S(2..|S|)}$ 的答案即可。若 $S_1=1$，则还要乘 $2$（此时存在 $2$ 个子集）。
$S_1$被压缩。我们枚举它压缩的长度 $L$ 以及周期个数 $n$，考虑 $S(1..nL)$ 这段字符，有多少子集能压缩成长度为 $L$ 的字符串。
对于一个周期 $S’$，当且仅当 $S’$ 是 $S(1..L),S(L+1..2L),\ldots,S((n-1)L+1..nL)$ 这些所有串的子集时，才是一个可能的周期。那么相当于 $S’$ 是 $S(1..L),S(L+1..2L),\ldots,S((n-1)L+1..nL)$ 这些字符串的按位与后的字符串的子集。
所以我们对这些串按位与后的串求出 $f$ 的值，也就求出这个前缀所有的方案数了。然后计算剩下那部分后缀的方案就可以了。
使用记忆化搜索来完成转移。压缩状态可以使用 unsigned __int128 来存储。
考虑这个东西的状态数。
令 $n=100$，长度不超过 $12$ 的串只有 $2^{12}=4096$ 个。长度至少 $13$ 的串，最多递归地倍长 $2$ 次。
对 $[2,2],[2,3],[3,2],[n(2\leq n\leq7)]$ 的压缩分别考虑即可（搬 yhx）。
可以得到一个非常松的界 $O(n^4)$。
Code：
#include<map>
#include<cstdio>
#include<cstring>
#define lg2(x)(63-__builtin_clzll(x))
using namespace std;
typedef unsigned __int128 u128;
typedef unsigned long long uLL;
const int md=998244353;
map<u128,int>f;
char s[128];
int n;
inline int lg(const u128&x){return(x>>64?lg2((uLL)(x>>64))+64:lg2((uLL)x));}
int dfs(const u128&b){
if(f.count(b))return f[b];
int&F=f[b],L=lg(b);
F=(1+(uLL)(b&1))*dfs(b>>1)%md;
for(int l=1;l<<1<=L;++l){
u128 t=b&(((u128)1<<l)-1),s=b>>l;
for(int i=2;i*l<=L;++i){
t&=s&(((u128)1<<l)-1),s>>=l;
F=(F+(uLL)dfs(t|((u128)1<<l))*dfs(s))%md;
}
}
return F;
}
int main(){
scanf("%s",s);
int L=strlen(s);
u128 n=1;
for(int i=0;i<L;++i)n=n<<1|(s[i]&15);
f[1]=1;
printf("%d\n",dfs(n));
}