题解 P7740 [NOI2021] 机器人游戏

mzgwty · 2021-07-30 22:07:47 · 题解

更新了一下，那天晚上因为太赶，DP 的那部分好像不是很能让人理解，然后出现了一些明显的错误，引起了一些不必要的疑惑，在这里说句抱歉

首先声明，这是一个来自场外选手的题解，然后其目的是为了能让大部分人看懂，因为这题考察的完全是 noip 范围内的东西，所以个人认为很有价值，值得好好说一下

当然这也不算自己的题解，其实是读懂了某个场内选手的代码之后写出来的东西

首先来看最基础的容斥该怎么做

我们先预处理出来每个机器人向右移动 i 步后会对那个位置造成什么改变，把这个改变记作 v_i

若 v_i=0，表示当前位置不用变化

若 v_i=1，表示当前位置需要从 0 变为 1 或者从 1 变为 0

若 v_i=2，表示当前位置为 0

若 v_i=3，表示当前位置为 1

然后这段预处理大概长这样

v[0]=0;
for(int i=0 ; i<len ; ++i)
    if(s[i]=='R') v[++p]=0;
    else if(s[i]=='0') v[p]=2;
    else if(s[i]=='1') v[p]=3;
    else v[p]^=1;

然后维护一个 mask_i，表示 v=i 的位置的集合，可以用一个 long long 类型的变量存下来

然后对于每个位置 i，维护一个 msk_j，表示从这个点出发时每种 v_j 形成的集合

然后由于有在这个点右侧的位置，也有这个点根本到达不了的位置，这些位置我们就给它赋成 0

然后我们就可以求出所有 2^n 种选法每种 v 所对应的位置集合

for(int i=0 ; i<4 ; ++i) mask[i]=0;
for(int i=0 ; i<p ; ++i) mask[v[i]]|=1ull<<i;
for(int S=0 ; S<(1<<n) ; ++S)
    for(int i=0 ; i<4 ; ++i)
        msk[S][i]=0;
for(int i=0 ; i<n ; ++i) {
    for(int j=0 ; j<4 ; ++j) msk[1<<i][j]=mask[j]<<(l-i-1);
    msk[1<<i][0]|=(1ull<<(n-1-i))-1,msk[1<<i][0]|=(1ull<<n)-(1ull<<(n-1-i+p));
}
for(int S=0 ; S<(1<<n) ; ++S)
    for(int j=0 ; j<4 ; ++j)
        msk[S][j]=msk[S^(S&-S)][j]|msk[S&-S][j];

然后我们就需要求出每种状态在当前这一个机器人时的方案数

注意：这里的 i 指的不是从左往右数的第 i 个，而是从右往左数第 i 个，至于为什么，待会儿会说

不难发现，如果 msk_{S,0} 和 msk_{S,1} 有交集，那么它们交集这些位置必须为空，因为不可能存在一个数既是 0 又是 1。msk_{S,2} 与 msk_{S,3} 同理。记这个为 emp

然后如果某个位置既被 msk_{S,0} 或者 msk_{S,1} 包含，又被 msk_{S,2} 或者 msk_{S,3} 包含，那么这个位置只能选 0 或者只能选 1，记这个为 rct

然后 rct 与 emp 取个并集得到被限制了的位置

这样在 emp 中的位置只能有 1 种选法，就是空格子，在 rct 中而不在 emp 中的位置则有 2 种选法，剩下的位置则有 3 种选法，那么用 2 的次幂乘上一个 3 的次幂就是这个状态在当前这行的方案数了，把每种状态在每一行的方案乘起来就是总方案数，然后按照题面上的东西做一个容斥就行了

for(int S=0 ; S<(1<<l) ; ++S) {
    emp[S]=(msk[S][0]&msk[S][1])|(msk[S][2]&msk[S][3]);
    rct[S]=(msk[S][0]|msk[S][1])&(msk[S][2]|msk[S][3]);
    rct[S]|=emp[S];
    int c1=get(emp[S]),c2=get(rct[S]);
    nw[S]=1ll*pw3[n-c2]*pw2[c2-c1]%P,f0[S]=1ll*f0[S]*nw[S]%P;
}

然后这就是一个 m2^n 的做法，n \le 16 的情况已经完全能过了。

然后我们先观察特殊性质 A,B，发现这两个性质是一个常见的状压DP，直接把后面 p 个位置是否被选择为可行的位置压成新的一维。

当然这不是重点

大型比赛的部分分大部分都会告诉你正解的方向，这道题也不例外，说明正解需要用到状压 DP

观察数据范围，n\le32，这个数是 32 而不是 70,100 之类常见 n^k 算法的标准范围，我们可以考虑折半，把左一半先弄出来再来想右半部分该怎么弄。

此时左半部分变成了 n\le16，可以直接使用刚才提到的容斥的方法计算，但计算出来的所有方案必定至少包含左半部分的一个位置，那么我们接下来需要计算不包含左半部分位置的方案数

此时先维护两个新的数组 f1_{i,S},f2_{i,S}

令左半部分最右侧的位置为 pos