关于转移方程的解释：

考虑一个 $01$ 串 $S$，由题目中的性质二，我们考虑枚举断点位置 $k$，统计左右两边的编码方案，然后再乘起来。即：

$$dp_{l,r}=\sum_{k=l}^{r-1}{dp_{l,k}dp_{k+1,r}}$$

同时由性质三，我们知道任何一个串可以被拆成多个循环，那么我们就可以考虑每一个循环内的拆分方案，再在外面套一个 $\times$ 就行了，也就是在只考虑循环的情况下：

$$f_{l,r}=\sum_{d|(r-l+1)}[d\text{为}[l,r]\text{的循环节}]{dp_{l,l+d-1}}$$

那么既然我们知道了拆循环的方案数，那么我们在枚举时不妨直接假设把前一段括上，再去考虑后一段。也就是：

$$dp_{l,r}=\sum_{k=l}^{r-1}{g_{l,k}dp_{k+1,r}}$$

如果还不理解可以这么想：

对于一个长度为 $n$ 串 $S$，我们在枚举时直接将 $S_{1,k_1}$ 括起来，有 $g_{1,k_1}$ 种方案，然后去考虑 $S_{k_1+1,n}$。

那我们考虑 $S_{k_1+1,n}$ 的时候，我们再直接将 $S_{k_1+1,k_2}$ 括起来，有 $g_{k_1+1,k_2}$ 种方案，再去考虑 $S_{k_2+1,n}$。

以此类推。

Solution

考虑对于一个固定的$0/1$串如何求解方案数，可以通过区间dp，设$f_{l,r}$表示将区间$[l,r]$编码的方案数，$g_{l,r}$表示将区间$[l,r]$编码成单个字符或由一个括号括起来（允许嵌套）的方案数，转移时考虑第一位是否编码成一个字符

$$\begin{aligned} f_{l,r}&=\sum_{k=l}^{r-1}g_{l,k}f_{k+1,r}\\ g_{l,r}&=\sum_{d|r-l+1} [d为[l,r]的循环节]f_{l,l+d-1} \end{aligned}$$

接下来考虑原问题，设$f_S$表示$S$及其所有子集的方案数， 在$g$的转移中枚举$d$后将划分出的子串并起来再进行转移，使用map来存储并记忆化搜索即可。

复杂度$T(n)=\sum_{i=1}^n(n-i+1)(1+\sum_{d|i}(i+T(d))$，简单打个表可以发现当$n=100$时，$T(n)=243422222$，能过。

Code

/*
Problem : 
Algorithm : 
Status : 
*/
#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#define DEBUG cerr << "Passing Line " << __LINE__<< " in Function [" << __FUNCTION__ << "].\n";
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> inline bool checkMax(T &a,const T &b) {return a < b ? a = b,1 : 0;}
template<typename T, typename...Args> inline void checkMax(T &a,const Args...arg) {checkMax(a,max(arg...));}
template<class T> inline bool checkMin(T &a,const T &b) {return a > b ? a = b,1 : 0;}
template<typename T, typename...Args> inline void checkMin(T &a,const Args...arg) {checkMin(a,min(arg...));}

const int INF = 0x3f3f3f3f;
const ll llINF = 1e18;
const int MOD = 998244353;
const int MAXN = 105;

void addmod(int &x,int y) {x += y; if(x >= MOD) x -= MOD;}
void submod(int &x,int y) {x -= y; if(x < 0) x += MOD;}
int add(int x,int y) {addmod(x,y); return x;}
int sub(int x,int y) {submod(x,y); return x;}

string s;
map<string,int> f,g;

int GetG(string s);

int GetF(string s){
    if(s == "") return 1;
    if(f.count(s)) return f[s];
    int n = s.length(), res = 0;
    for(int i = 1;i <= n;i++)
        addmod(res,1ll * GetG(s.substr(0,i)) * GetF(s.substr(i,n - i + 1)) % MOD);
    return f[s] = res;
}

int GetG(string s){
    if(s == "") return 1;
    if(s == "0") return 1;
    if(s == "1") return 2;
    if(g.count(s)) return g[s];
    int n = s.length(), res = 0;
    for(int d = 1;d < n;d++){
        if(n % d != 0) continue;
        string t = "";
        for(int i = 0;i < d;i++){
            bool x = 1;
            for(int j = i;j < n;j += d) x &= s[j] - '0';
            t += x + '0';
        }
        addmod(res,GetF(t));
    }
    return g[s] = res;
}

int main(){
    cin >> s;
    printf("%d\n",GetF(s));
    return 0;
}

AGC020E

题

我是先想的如果 1 不能变 0 应该怎么做，明显是个区间 DP。 $f_{i,j}$ 代表 $[i,j]$ 方案数，$g_{i,j}$ 代表缩成一个括号（以及只有一个字符的情况，0 或 1）$f$ 转移的时候枚举最后一个括号位置。$g$ 转移就枚举区间长度 $len$ 的约数（$len$ 除外）把这些缩成一个括号。

这题 $f$ 还是一样的转移方式，不过算 $g$ 的时候不同了，需要转移自的 $f$ 需要是所有截取部分 AND 起来的值，可能会产生新的字符串，所以 DP 状态里就记字符串而不是区间了，记忆化搜索即可。

这个东西看起来复杂度很大但其实是对的，首先 $f$ 刷出来的 $f$ 不用考虑，因为 $f$ 刷出来的 $f$ 刷出来的 $f$ 一定都是原来 $f$ 的字串，还只有 $n$ 个。而 $f$ 也会产生 $g$，并且 $f$ 的每一个子串都会产生一个 $g$ 的计算，而 $g$ 又会产生新的 $f$，这些产生出来的 $f$ 是必须全部重新算的。

但是每次产生出来的 $f$ 长度至多是原来 $g$ 的一半，三次 $g$ 产生 $f$ 操作以后，长度就必定 $\leq 13$ 了。长度为 $n$ 的 01串只有 $2^n$ 个，当 $n\leq 13$ 的时候这其实并不大。

所以我们只需要考虑 $g$ 变 $f$ 一次和两次的情况就行了，而且分成 $f$ 的次数两次乘起来还得小于 $8$，不然就长度太小了。其实最后生成的串可以看作是最早的原串取了几个字串拼起来的，这里用两次操作长度都减半举例好了。

只用 $i,j,k$ 就可以表示一个状态，那么状态数不会超过 $n^3$。 两次分别为分两段和分三段其实是一样的，状态数也只有 $n^3$ 级别种。 实际值是远小于理论值的。

一共有 $n^3+2^{\frac{n}{8}}$ 个状态，转移用时 $n^2$，时间复杂度 $O(n^5+n^2 2^{\frac{n}{8}})$

代码写得很丑（）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <string>
using namespace std;
typedef long long LL;
const LL N = 998244353;

map <string,LL> mp[2];
string u;

LL f(LL id,string s){
	if(mp[id].find(s) != mp[id].end()) return mp[id][s];
	LL ret = 0,len;
	len = s.length();
	if(id){
		for(LL i = 0;i < len;i ++) ret = (ret + f(1,s.substr(0,i)) * f(0,s.substr(i,len))) % N;
		mp[id][s] = ret; return ret;
	}
	else{
		for(LL i = 1;i < len;i ++){
			if(len % i) continue;
			string t = "";
			for(LL j = 0;j < i;j ++) t += '1';
			for(LL j = 0;j < len;j += i){
				for(LL k = 0;k < i;k ++){
					if(s[j + k] == '0') t[k] = '0';
				}
			}
			ret += f(1,t); ret %= N;
		}
		mp[id][s] = ret; return ret;
	}
}

int main(){
	mp[0][""] = mp[1][""] = 1;
	mp[0]["0"] = 1; mp[0]["1"] = 2;
	mp[1]["0"] = 1; mp[1]["1"] = 2;
	cin >> u;
	cout << f(1,u) << '\n';
	return 0;
}