感觉只会抄题解。。

AGC020E

首先自己可以想到如果只是要单纯的求一个串的方案数可以区间 dp：观察这个表达式，可以写成

f := g | g + f
g := '0' | '1' | '(' + f + '*' + 'x' +  ')'

其中 x 是一个数字，要求 $x>1$，并且 $f$ 是 $g$ 的一个长度为 $x$ 的循环节。

那么就可以根据上面的定义写出 dp 了：设 $f_{l,r},g_{l,r}$ 表示区间 $[l,r]$ 的答案，根据上面的定义可以得到转移：

$$ \begin{aligned} f_{l,r} &= g_{l,r}+\sum_{i=l}^{r-1} g_{l,i}f_{i+1,r}\\ g_{l,r} &=\begin{cases} 1& l = r\\ \sum_{d|(r-l+1),d < r-l+1}[\text{d 是 s[l,r] 的循环节}] f_{l,l+d-1}& \text{otherwise} \end{cases}\\ \end{aligned} $$

接下来就看题解了。

题解里说，我们把状态改成 $f_s$ 表示字符串 $s$ 的所有子串的方案数，然后类似做就好了。这时候转移 $f$ 就是枚举断开，$g$ 就是枚举循环节，将所有长度为 $d$ 的子串的按位与拿下去做。这样看起来十分暴力，但是我们可以推一下复杂度：设 $T_f(n)$ 表示长度为 $n$ 的 $f$ 的计算时间，$T_g(n)$ 表示长度为 $n$ 的 $g$ 计算时间，有（这里要注意 时间是相加不是相乘）：

$$ T_f(n) = \sum_{i=1}^n (n-i+1)T_g(i)\\ T_g(n) = \sum_{d|n,d < n} T_f(d)\\ \Rightarrow T_f(n) = \sum_{i=1}^n (n-i+1)\sum_{d|i,d < i} T_f(d) $$

注意这里第一行是乘 $n-i+1$ 而不是加 $T_f(n-i)$ 的原因 $f$ 不会生成新的串，只会导致 $g$ 被多算几遍，那么一个 $g$ 会被枚举 $n-len+1$ 次。这样大概运算是 29310258 反正能过（

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb push_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100+5;
const int ha = 998244353;
std::string str;

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

std::map<std::string,int> f,g;
int F(std::string);
int G(std::string);

inline int F(std::string s){
    if(s.empty()) return 1;
    if(f.count(s)) return f[s];
    int res = 0;
    FOR(i,1,SZ(s)) add(res,1ll*G(s.substr(0,i))*F(s.substr(i,SZ(s)-i))%ha);
    f[s] = res;return res;
}

inline int G(std::string s){
    if(s.empty()) return 1;
    if(s == "0") return 1;
    if(s == "1") return 2;
    if(g.count(s)) return g[s];
    int res = 0;
    FOR(d,1,SZ(s)-1){
        if(SZ(s)%d) continue;
        std::string nxt="";
        FOR(i,0,d-1){
            bool flag = 1;
            for(int j = i;j < SZ(s);j += d) flag &= (s[j]=='1');
            if(flag) nxt += "1";
            else nxt += "0";
        }
        add(res,F(nxt));
    }
    return res;
}

int main(){
    std::cin >> str;
    printf("%d\n",F(str));
    return 0;
}