题解 AT3859 【[AGC020E] Encoding Subsets】

· · 题解

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;
}