题解 [AGC020E] Encoding Subsets

· · 个人记录

一开始的时候是毫无头绪的。

但是想一想，你可以发现len很小，是个可以区间dp的东西。

那怎么办呢？

我们现在有两种合并方法：第一种是取len的因子合并，第二种是任意合并，第二种不会套括号，所以不会与第一种冲突。

他既然是要求所有子集，我们可以就让f[l,r]表示[l,r]内所有子集的答案。我们就能发现，因子合并的转移将会取所有段的并运算作为合并上来的东西。

我们大力猜测即使加上了并运算，dp的状态数也不会太多，就可以对第一种合并暴力执行。

所以不能使用普通的区间dp，需要记忆化。

现在比较麻烦的是第二种情况，因为直接合并是会算重的。一开始是想记另外一个状态g表示第一个括号在哪里开始来合并，但是这样反而复杂化了问题；更好的方法是将括号接在一个任意数后方来进行第二种转移，这样就不会重了。

另外这题可以锻炼你使用位运算的能力

/*************************************************************************
    > File Name: AGC020E.cpp
    > Author: The-Out-Land
    > Mail: [email protected] 
    > Created Time: 2020年11月12日 星期四 11时28分34秒
 ************************************************************************/

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define enter putchar('\n')
#define space putchar(' ')
#define re register
#define int long long
#define ll __int128
#define Vec vector<int>
#define N 210
#define Pii pair<ll,int>
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second

using namespace std;

const int mod=998244353;

ll s,S;

char t[N];

map<Pii,pii> P;

int n,f[N][N],g[N];

Vec di[N];

inline int max(int x,int y){return (x>y?x:y);}

inline int min(int x,int y){return (x<y?x:y);}

inline ll read(){
    ll x=0;char c=getchar();bool y=1;
    for(;c<'0' || c>'9';c=getchar()) if(c=='-') y=0;
    for(;c>='0' && c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-48;
    if(y) return x;
    return -x;
}

int st[100],top;

inline void write(ll x,char c){
    if(x<0) putchar('-');
    while(x) st[++top]=x%10,x/=10;
    if(!top) putchar('0');
    while(top) putchar(st[top--]+'0');
    putchar(c);
    return;
}

inline int add(int x){
    if(x<0) return x+mod;
    return (x>=mod?x-mod:x);
}

inline void merge(ll x,int w){
    if(P.find(mp(x,w))!=P.end()) return;
    if(w==1) return P[mp(x,w)]=mp((int)x+1,x+1),void();
    int sz=di[w].size(),d,ans=0,ans2=0,tot=1;
    ll now,U;
    for(re int i=0;i<sz;++i){
        d=w/di[w][i];
        now=U=(1ll<<d)-1;
        for(re int j=0;j<w;j+=d){
            now&=(x>>j&U);
        }
        merge(now,d);
        ans=add(ans+P[mp(now,d)].fi);
    }
    for(re int i=1;i<w;++i){
        merge(x>>i,w-i);
        merge(x^(x>>i<<i),i);
        ans2=(ans2+P[mp(x^(x>>i<<i),i)].fi*P[mp(x>>i,w-i)].se)%mod;
    }
    return P[mp(x,w)]=mp(add(ans+ans2),ans),void();
}

inline void Input(){
    scanf("%s",t+1);
    n=strlen(t+1);

    for(re int i=n;i;--i)
    S=(S<<1)+(t[i]^'0');

    for(re int i=2;i<=n;++i){
        for(re int j=i;j<=n;j+=i)
        di[j].push_back(i);
    }
    return;
}

inline void solve(){
    merge(S,n);
    printf("%lld\n",P[mp(S,n)].fi);
    return;
}

signed main(){
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    Input();
    solve();
    return 0;
}

真不错啊。。