题解P10926【Happybob's Magic (UBC001F)】

xuanxuan001 · 2024-08-24 20:10:21 · 题解

抽象的官解，爽飞的四天。

发现两种操作都是整体的批量操作而没有针对单点的，所以感性理解一下这些操作是很不“自由”的，推理一下发现确实如此。

由于 D 操作针对元素而不是序列，所以下面直接认为序列是所有为 1 位置构成的集合，D(A) 表示对 A 进行一次 D 操作后的集合。

首先，如果进行了一次 D 操作后，那么再次进行 D 操作不会改变，但如果取反（就是 B 操作，这么说直观一些，下同）后会发现只要它不是空集，那么它就拥有至少一半的元素（即值是 1）。那么猜想这个序列进行一次 D 操作后一定会变成全集，证明如下：

发现所有的情况都严格不劣于恰有 2^{n-1} 个元素的情况，也就是操作前的集合（设它为 A）的线性基大小为 n-1。那么此时不妨设线性基中没有 1 （即最高位是 2^0）。那么取反后一定满足 1 在集合里面，而 \forall x \in (0,2^n-1) 一定有 x \in A 或 x \oplus 1 \in A，因此如果再进行一次 D 操作就一定有 x,x \oplus 1 \in D(A)，因此可知 D(A) = U。

同样的，也可以得到 A 和它的补集中至少有一个进行 D 变换后会变成全集。

那么有了这些结论，就不难发现可能的集合只有 O(1) 种，经过梳理，发现有八种：

3. U
4. \emptyset

对于第五条的解释：D(\emptyset) = \{0\}。

因此只需要用一个数就能存储整个集合，并实现 O(1) 单次变换和查询。

其实这里跟官解前面的那些观察差不多。

每次需要变换一个区间，这是容易维护的，线段树即可维护，记录每个节点的函数值以及每种数列的经过次数即可。总复杂度 O(n2^n +8^2m + 8q\log m)，把 8 认为和 \log m 同阶的话甚至刚好平衡了，不用上猫树。

可能复杂度有些高？官解最后靠循环节直接计算倒也是个思路，主要是利用了 BD 两个操作连续进行多次都没有意义，幸好没卡我的。但我觉得代码复杂度肯定是我优。

代码

#include<cstdio>
#define TY int
#define MAXN 262144
#define FOR(i,a,b) for(TY i=(a);i<=(b);i=-~i)
#define fOR(i,a,b) for(TY i=(a);i<(b);i=-~i)
#define ROF(i,a,b) for(TY i=(a);i>=(b);i=~-i)
#define rOF(i,a,b) for(TY i=(a);i>(b);i=~-i)
#define EDG(i,u) for(TY i=hed[u];i;i=nxt[i])
using namespace std;
typedef long long ll;
const TY M=998244353;
typedef unsigned long long ull;
TY _abs(TY a){return a<0?-a:a;}
TY maxn(TY a,TY b){return a>b?a:b;}
TY minn(TY a,TY b){return a<b?a:b;}
inline void updmx(TY &x,TY y){if(x<y)x=y;}
inline void updmn(TY &x,TY y){if(x>y)x=y;}
inline void add(TY &x,TY y){if((x+=y)>=M)x-=M;}
TY gcd(TY a,TY b){return b?gcd(b,a%b):a;}
TY qp(TY a,TY b){TY ans=1;do{if(1&b)ans=ans*a%M;a=a*a%M;}while(b>>=1);return ans;}
char getc(){char ch=getchar();while(ch==' '||ch=='\n'||ch=='\r')ch=getchar();return ch;}
TY qr(){
    char ch=getchar();TY s=0,x=1;
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')x=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0';return x*s;
}void qw(TY a){if(a>9)qw(a/10);putchar(a%10+'0');}
void qw(TY a,char ch){
    if(a<0){a=-a;putchar('-');}
    if(a>9)qw(a/10);putchar(a%10+'0');
    if(ch)putchar(ch);
}TY n,m,T,b[MAXN],ct,kd,x,l,r,to[2][8],ar[18],nm,tot[MAXN][8],vl[8],ans;
TY tre[MAXN<<1][8],sm[MAXN<<1][8][8],tmp[8];
bool a[MAXN],t[MAXN];char s[MAXN];
//集合编号按题解中列举顺序，0代表B变换，1代表D变换
void ins(TY x){
    ROF(i,n-1,0)if((1<<i)&x){
        if(ar[i]){x^=a[i];continue;}
        ar[i]=x;++nm;return;
    }
}void dfs(TY x,TY v){
    if(x==n){t[v]=true;return;}
    dfs(x+1,v);if(ar[x])dfs(x+1,v^ar[x]);
}void build(TY i,TY j,TY id){
    if(i==j){
        if(s[i]=='B')fOR(i,0,8){
            tre[id][i]=to[0][i];
            sm[id][i][to[0][i]]=1;
        }else fOR(i,0,8){
            tre[id][i]=to[1][i];
            sm[id][i][to[1][i]]=1;
        }return;
    }TY mid=i+j>>1,sn=id<<1;
    build(i,mid,sn);build(mid+1,j,sn|1);
    fOR(i,0,8){
        tre[id][i]=tre[sn|1][tre[sn][i]];
        fOR(j,0,8)sm[id][i][j]=sm[sn][i][j]+sm[sn|1][tre[sn][i]][j];
    }
}void ask(TY i,TY j,TY id){
    if(l<=i&&j<=r){
        fOR(i,0,8)tmp[i]+=sm[id][x][i];
        x=tre[id][x];return;
    }TY mid=i+j>>1;
    if(l<=mid)ask(i,mid,id<<1);
    if(r>mid)ask(mid+1,j,id<<1|1);
}int main(){
    fOR(i,0,8)to[0][i]=i^1;
    to[1][2]=2;to[1][3]=4;
    to[1][4]=4;to[1][5]=6;
    to[1][6]=6;to[1][7]=4;
    n=qr();m=qr();T=qr();
    fOR(i,0,1<<n)a[i]=qr();scanf("%s",s+1);
    if(n==1){to[1][0]=0;to[1][1]=1;}//n=1需要特殊考虑
    else{
        fOR(i,0,1<<n)if(a[i])ins(i);
        if(nm==n)to[1][0]=4;
        else{dfs(0,0);to[1][0]=2;}
        fOR(i,nm=0,n)ar[i]=0;
        fOR(i,0,1<<n)if(!a[i])ins(i);
        if(nm==n)to[1][1]=4;
        else{dfs(0,0);to[1][1]=2;}
    }fOR(i,0,1<<n)if(a[i])++vl[0];vl[1]=(1<<n)-vl[0];
    fOR(i,0,1<<n)if(t[i])++vl[2];vl[3]=(1<<n)-vl[2];
    vl[4]=1<<n;vl[6]=1;vl[7]=(1<<n)-1;build(1,m,1);
    while(T--){
        kd=qr();
        if(kd==2){
            x=qr();l=qr();
            switch(b[x]){
                case 0:qw(a[l],'\n');break;
                case 1:qw(a[l]^1,'\n');break;
                case 2:qw(t[l],'\n');break;
                case 3:qw(t[l]^1,'\n');break;
                case 4:printf("1\n");break;
                case 5:printf("0\n");break;
                case 6:qw(!l,'\n');break;
                case 7:qw(!!l,'\n');break;
            }continue;
        }if(kd==1){
            x=qr();l=qr();r=qr();x=b[x];
            fOR(i,0,8)tmp[i]=0;ask(1,m,1);
            b[++ct]=x;qw(vl[b[ct]],'\n');
            fOR(i,0,8)tot[ct][i]=tmp[i];
        }else{
            x=qr();l=qr();ans=tot[x][4];
            if(a[l])ans+=tot[x][0];else ans+=tot[x][1];
            if(t[l])ans+=tot[x][2];else ans+=tot[x][3];
            if(l)ans+=tot[x][7];else ans+=tot[x][6];qw(ans,'\n');
        }
    }return 0;
}