AGC020E Encoding Subsets

申必题，搞了点奇怪做法跑过去了。

其实要做的就是对于每个编码方案，求出每个编码方案最终二的 $1$ 的个数次幂。

现在假设我有一种编码策略，很显然如果所有数都是 $0$ 这种策略一定是合法的，但是该怎么求出这种策略下最多的 $1$ 的个数？

可以发现对于某个数假设它被嵌套编码了若干层，这些层用来循环的长度分别为 $A_1,A_2,\ldots,A_k$ ，那么可以发现它是否合法只和这些长度有关，和这些编码段在原序列的位置无关。具体来说只需要关心它的位置加上这些长度的一个子集的所有位置是否都是 $1$ ，如果都是就可以 $1$ ，否则在这里的编码就一定是 $0$ 。

知道这一点后可以猜测实际这样的状态是不多的，对每个区间考虑它的这些长度的一个方案设成一个状态，打表发现状态总数是 $10^8$ 级别的。转移过程就是考虑区间开头是直接作为一个数还是开头进行一次缩段。

STD：直接暴力，复杂度是对的。心态有点崩。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "unordered_map"
#include "cassert"
#include "bitset"
#include "queue"
using namespace std;
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#pragma GCC optimize(3)
typedef long long ll;
const int MAXN = 106;
const int P = 998244353;
int n;
char S[MAXN];
int A[MAXN];
bitset<102> s;

inline bool judge( int ps , bitset<102> vec ) {
//    return true;
    return ( ( s >> ps ) & vec ) == vec;
}

unordered_map<bitset<102>,int> F[MAXN][MAXN];
int calc( int l , int r , bitset<102> vec ) {
    if( l == r + 1 ) return 1;
    if( F[l][r].count( vec ) ) {
        return F[l][r][vec];
    }
    int ans = 0 , w = 1;
    if( judge( l , vec ) ) w = 2;
    ans = ( ans + w * 1ll * calc( l + 1 , r , vec ) ) % P;
    auto vv = vec;
    rep( len , 1 , ( r - l + 1 ) / 2 ) {
        int cc = 0;
        for( int k = 1 ; ( k + 1 ) * len + l - 1 <= r ; ++ k ) {
            vv |= vv << len;
            ans = ( ans + calc( l , l + len - 1 , vv ) * 1ll * calc( l + len * ( k + 1 ) , r , vec ) ) % P;
        }
        vv = vec;
    }
    return F[l][r][vec] = ans;
}

void solve() {
    scanf("%s",S + 1);
    n = strlen( S + 1 );
    rep( i , 1 , n ) A[i] = S[i] - '0' , s[i] = A[i];
    bitset<102> ii;
    ii.set( 0 );
    cout << calc( 1 , n , ii ) << endl;
//    rep( i , 1 , n ) rep( j , i , n ) {
//        cout << i << ' ' << j << ' ' << pr[i][j] << endl;
//    }
//    cout << pp << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}