AGC020E Encoding Subsets 题解

· · 题解

首先考虑对于一个确定的长度为 n 的 \texttt{01} 串 S，如何求 S 的编码方式数。

设 f_{l,r} 表示 S_l\sim S_r 的编码方式数，g_{l,r} 表示 S_l\sim S_r 缩成一个括号或单个字符的编码方式数。

对于 f_{l,r}，枚举 S_l\sim S_r 编码后第一个字符的来源，得到转移方程：

f_{l,r}=\sum_{m=l}^{r} g_{l,m} \times f_{m+1,r}

对于 g_{l,r}，枚举 S_l\sim S_r 的循环节 d，得到转移方程：

g_{l,r}=\sum_{d\mid len,d \ne len} w(d,l,r) \times f_{l,l+d-1}

其中，len=r-l+1，若 d 为 S_l\sim S_r 的循环节则 w(d,l,r)=1，否则 w(d,l,r)=0。

直接计算即可得到 S 的编码方式数 f_{1,n}。

接下来考虑如何计算长度为 n 的 \texttt{01} 串 S 的所有子集的编码方式数之和。

同理，设 f_S 表示 S 的所有子集的编码方式数之和，g_S 表示 S 的所有子集的缩成一个括号或单个字符的编码方式数之和。

对于 f_S，仍然枚举 S 编码后第一个字符的来源，得到转移方程：

f_S=\sum_{m=1}^{n} g_{S[1,m]} \times f_{S[m+1,n]}

对于 g_S，同样枚举 S 的循环节 d，得到转移方程：

g_S=\sum_{d \mid n,d \ne n} f_{c(S,d)}

其中 c(S,d) 表示，把 S 分成长度为 d 的 \dfrac{n}{d} 个 \texttt{01} 串，每个 \texttt{01} 串按位与的结果。

记忆化搜索即可。有效状态数并不多，足以通过。

const int mod=998244353;
string s;
map <string,int> f,g;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ad(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
int G(string s);
int F(string s){
    if(s=="") return 1;
    if(f.count(s)) return f[s];
    int n=s.size(),ans=0;
    for(int i=1;i<=n;i++) add(ans,1ll*G(s.substr(0,i))*F(s.substr(i,n-i))%mod);
    return f[s]=ans;
}
int G(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.size(),ans=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]=='1');
            t+=x+'0';
        }
        add(ans,F(t));
    }
    return g[s]=ans;
}
void solve(){
    cin>>s;
    cout<<F(s)<<endl;
}