题解：P7740 [NOI2021] 机器人游戏

pxb0801 · 2026-07-19 21:41:02 · 题解

分析

观察题面，发现神秘的样例解释 2，每一句都在告诉我们：对起点集合容斥。

那么就按照这个做法，考虑对于单个机器人的单个位置，它会受到某个起点位置怎样的限制。

容易发现，限制形如 0,1,x,1-x，即赋 0、赋 1、不变，取反。于是，对于每个位置，用 4 个 bool 变量来表示是否受到这 4 种限制。因此，对于每个位置，可以根据其受到了哪些限制，得到这个位置的方案数。

显然每个机器人是独立的，因此我们直接用 bitset 压缩这 m 个机器人的信息。

::::info[如何得到每个位置受到哪些限制？] 定义一个 node 包含 4 个 bitset，分别表示 4 种限制是否在每个机器人用。

设 op_{i,j} 表示离起点第 i 个位置，第 j 个机器人会受到哪个限制，同样用 bitset 压缩。

那么初始 2 限制都为 true，然后根据输入序列扫描即可。 :::: ::::info[如何得到方案数？] 首先，如果同时存在 0,1 或 x,1-x，那么该位置只能为空。

否则如果 4 个限制存在 2 个，那么除空之外，有且仅有 1 种，共 2 种。

否则只有 1 个，那么除空外有 2 种，共 3 种。

没有限制的情况不可能，因为每个位置要么被机器人修改要么没有，没有修改那么会受到 2 限制，即不变。 ::::

做法 1

直接枚举起点集合。

考虑依次填每个机器人的第 p 位，枚举起点集合，设 lim_{i,j} 表示起点集合为 i，第 j 个机器人，对 p 位置的限制有哪些。

考虑使用子集递推减少枚举每一个起点位置的复杂度，设 dis 表示 p 离最近的起点的距离，即 dis\gets p-\log_2 \operatorname{lowbit}(i)。那么有 lim_{i,j}\gets lim_{i-\operatorname{lowbit(i)},j} \vee op_{dis,j}。显然如果存在起点位置大于 p，那么说明该起点给 p 的限制是 2，或上只有 2 限制的变量即可。

接下来对于每个起点集合计算 p 位置的贡献，乘上 lim_i 的方案数即可，计算方法如上。但是，如果某个起点位置会让某个机器人爆炸，那么这个机器人的方案就不能算在里面。定义 ban_i 最右起点为 i 时，哪些机器人不会爆炸，在计算贡献的时候只计算不会爆炸的机器人即可，其他的是 1，不用计算。

注意初始化时根据集合大小的奇偶性决定是 1 还是 -1。

做法 2

考虑每一位是否作为起点，这样进行 dp。

考虑到最右起点关系到机器人是否会爆炸的特殊性，我们枚举最右起点位置，然后依次考虑每一位是否作为起点。

设最右起点位置为 w，那么如果机器人的移动位移大于等于 n-w，该机器人会爆炸，方案数为 1。因此有意义的机器人移动位移必然小于 n-w，也就是说会对当前位置 p 有限制的起点位置只会在 p 之前 n-w 个，如果再往前还有起点，只是相当于给 p 增加了一个 2 限制而已。

因此考虑类似滑动窗口的方式 dp：设 f_{i,0/1} 表示在当前位置 p（用滚动数组压掉），在与 p 距离为下标意义下的起点集合为 i，是否有更往前的起点，考虑前 p 个位置的填法的方案数。

同样设 lim_i 表示与当前位置距离为下标意义下的起点集合为 i 时的限制，同样使用子集递推即可。

预处理两个数组 ul_i,vl_i，分别表示起点集合为 i 的情况下，没有更往前的起点/有更往前的起点的方案数。注意，由于每个最右起点对应有意义的机器人集合不同，因此每次枚举最右起点都要重新计算 ul,vl，详见代码。

考虑转移，就是枚举当前位置是否要作为起点，以及是否有更往前的起点。分讨 p 和 w 的关系：

注意如果选，起点集合大小的奇偶性会发生改变，因此是转移是减方案数。

综合

我们发现两种做法的复杂度都是 O(\frac{nm2^n}{ \omega})，而 n 是 32，如果我们能将 n 的范围减半就好了。

我们发现做法 2 的复杂度和 2^{n-w} 有关。因此设 B=\frac{n}{2}，在最右起点位置 w\le B 时，使用做法 1，而 w>B 时使用做法 2，就将复杂度平衡到了 O(\frac{nm2^\frac{n}{2}}{\omega})。

code

::::success[code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7,M=1005;
int n,m,B;
ll pw2[M],pw3[M],f[65536],ans,f2[2][65536][2],ul[65536],vl[65536];
char s[105];
bitset<M> ban[32],R,tmp1,tmp2,tmp3;
struct node{
    bitset<M> b[4];
    node operator |(const node &x)const{
        node y;
        for(int i=0;i<4;i++) y.b[i]=b[i]|x.b[i];
        return y;
    }
    ll calc(){
        tmp1=R&~((b[0]&b[1])|(b[2]&b[3])),tmp2=tmp1&((b[0]|b[1])&(b[2]|b[3])),tmp3=tmp1^tmp2;
        return pw2[tmp2.count()]*pw3[tmp3.count()]%mod;
    }
}op[32],lim[65536],tw;
int lowbit(int x){
    return x&(-x);
}
ll calc2(node x){
    x.b[2].set();
    return x.calc();
}
int main(){
    cin>>n>>m;
    B=n/2;
    pw2[0]=pw3[0]=1;
    for(int i=1;i<=m;i++){
        tw.b[2].set(i);
        pw2[i]=pw2[i-1]*2%mod,pw3[i]=pw3[i-1]*3%mod;
    }
    for(int i=0;i<n;i++){
        op[i]=tw;
    }
    for(int i=1;i<=m;i++){
        scanf("%s",s+1);
        int len=strlen(s+1),nw=0,tp=2;
        for(int j=1;j<=len;j++){
            if(s[j]=='R'){
                op[nw].b[2].set(i,0);
                op[nw].b[tp].set(i);
                tp=2;
                nw++;
            }
            else if(s[j]=='1') tp=1;
            else if(s[j]=='0') tp=0;
            else tp^=1;
        }
        op[nw].b[2].set(i,0);
        op[nw].b[tp].set(i);
        for(int j=0;j<n-nw;j++){
            ban[j].set(i);
        }
    }
    f[0]=mod-1;
    for(int i=1;i<(1<<B);i++){
        f[i]=mod-f[i&(i-1)];
    }
    for(int p=0;p<n;p++){
        for(int i=1;i<(1<<B);i++){
            int dis=p-__lg(lowbit(i));
            if(dis<0) lim[i]=lim[i&(i-1)]|tw;
            else lim[i]=lim[i&(i-1)]|op[dis];
        }
        for(int i=1;i<(1<<B);i++){
            R=ban[__lg(i)];
            f[i]=f[i]*lim[i].calc()%mod;
        }
    }
    for(int i=1;i<(1<<B);i++){
        ans=(ans+f[i])%mod;
    }
    for(int i=1;i<(1<<n-B);i++){
        lim[i]=lim[i&(i-1)]|op[__lg(lowbit(i))];
    }
    for(int w=B;w<n;w++){
        memset(f2,0,sizeof(f2));
        f2[1][0][0]=mod-1;
        R=ban[w];
        for(int i=0;i<(1<<n-w);i++){
            ul[i]=lim[i].calc(),vl[i]=calc2(lim[i]);
        }
        for(int p=0;p<n;p++){
            memset(f2[p&1],0,sizeof(f2[p&1]));
            for(int i=0;i<(1<<n-w);i++){
                for(int op=0;op<2;op++){
                    int out=i>>(n-w-1)&1;
                    if(p<w){
                        int j=(i^(i&1<<n-w-1))<<1|1;
                        f2[p&1][j][op|out]=(f2[p&1][j][op|out]-f2[p+1&1][i][op]*vl[j]%mod+mod)%mod;
                        j--;
                        f2[p&1][j][op|out]=(f2[p&1][j][op|out]+f2[p+1&1][i][op]*vl[j])%mod;
                    }
                    else if(p==w){
                        int j=(i^(i&1<<n-w-1))<<1|1;
                        f2[p&1][j][op|out]=(f2[p&1][j][op|out]-f2[p+1&1][i][op]*(op|out? vl[j]:ul[j])%mod+mod)%mod;
                    }
                    else{
                        int j=(i^(i&1<<n-w-1))<<1;
                        f2[p&1][j][op|out]=(f2[p&1][j][op|out]+f2[p+1&1][i][op]*(op|out? vl[j]:ul[j]))%mod;
                    }
                }
            }
        }
        for(int i=0;i<(1<<n-w);i++){
            ans=(ans+f2[n-1&1][i][0]+f2[n-1&1][i][1])%mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}

::::