Lights Off (USACO Gold January 2023)

$N \leq 20$ ，应该往Bitmask DP的方向想，事实证明也确实是。

首先可以观察出来，switch的效果是XOR叠加的，所以状态之间存在很多等价的关系。那按照一次操作大约至少可以减少一个灯的情况来看，基本上 $N$ 次操作应该可以到达任意灯的结果状态。实际上，存在一个简单的bound， $3N$ 次可以到达任何状态：就是通过最多N次操作把所有switch关闭，然后通过打开-关闭开关的方式，每 $2$ 次关闭一盏灯，这样最多 $2N$ 次可以关闭所有灯。

定义DP： $dp[i][b]$ ：在开始灯全灭、开关全为 $0$ 的情况下，通过 $i$ 步，是否能让灯变成bitmask $b$ 对应的状态。有了这个，通过状态的线性叠加，就可以 $\mathcal{O}(N)$ 线性求解每个query。

DP的状态转化如下，在 $dp[i-1][b]$ 的基础上，新增最前面的第一步，这一步flip的switch的效果，到 $i$ 步之后，就是一个 $i$ 长的 $1$ 的串（任意位置）在 $b$ 上的XOR。所以（ $x$ 为所有连续 $i$ 位为1的bitmask）：

dp[i][b] |= dp[i-1][b \oplus x]

查询的执行时，我们模拟最初的灯的状态，在没有额外的开头操作的情况下，每一轮结束后的状态（程序中的li）。然后我们检测dp[i][li]是否为true，如果是true，则说明存在一个开关操作序列，可以产生和li一样的效果，也就是可以把灯全部熄灭，i就是最少需要的操作次数。

这个是卡着时间过的（ $3.8$ 秒），因为 $\mathcal{O}(n^2 2^n)$ （都在预处理），往下看有再优化掉 $\mathcal{O}(n)$ 的办法。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int T, n;
bool dp[61][1<<20];
 
int parse(char *s) {
    int r = 0;
    while (*s) r = (r << 1) + (*(s++) - '0');
    return r;
}
 
int rotr(int x) {       // rotate right in n bit window
    return (x >> 1) | ((x & 1) << (n-1));
}
 
int main() {
    scanf("%d %d", &T, &n);
 
    dp[0][0] = true;
    int bm = 0;
    for (int i = 1; i <= 3*n; i++) {
        bm ^= 1 << (i-1) % n;           // effect of a switch in round i
        for (int j = 0; j < n; j++) {
            for (int b = 0; b < (1 << n); b++)
                dp[i][b] |= dp[i-1][b ^ bm];
            bm = rotr(bm);              // cyclic rotate right
        }
    }
 
    for (int i = 0; i < T; i++) {       // answer queries
        char sa[25], sb[25];
        scanf("%s %s", sa, sb);
        int li = parse(sa), sw = parse(sb);
        for (int j = 0; j < 3*n; j++) {
            if (dp[j][li]) {
                printf("%d\n", j);
                break;
            }
            li ^= sw;
            sw = rotr(sw);
        }
    }
    return 0;
}

使用“代表状态”可以进一步优化之后的代码，准备一个rep[b]数组，返回b的"代表状态"， rep[b]==reo[b']当且仅当b和b'是循环移位的关系。这样的话，我们只需要在dp中保存所有代表状态的结果，对于任意状态b，dp[i][rep[b]]就给出了是否这个状态可到达。这样的dp，新增加一个switch的时候，就可以固定这个switch的位置，计算量少掉了 $\mathcal{O}(n)$ 。最后复杂度是 $\mathcal{O}(n 2^n)$ 。

另外，通过实际验证，应该不超过 $N$ 步就可以到任何状态，不需要3N，所以这个也可以常数优化。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
// 使用“代表状态”来减少O(n):
// rep[bm] == rep[bm']，当bm和bm'是循环移位关系
 
int T, n;
bool dp[61][1<<20];
int rep[1<<20];     // rep[x]: x的代表状态
 
int parse(char *s) {
    int r = 0;
    while (*s) r = (r << 1) + (*(s++) - '0');
    return r;
}
 
int rotr(int x) {       // rotate right in n bit window
    return (x >> 1) | ((x & 1) << (n-1));
}
 
int main() {
    scanf("%d %d", &T, &n);
 
    fill(rep, rep+(1<<n), -1);
    for (int i = 0; i < 1<<n; i++)      // prepare rep[]
        if (rep[i] == -1) {
            int j = i;
            while (rep[j] == -1) {
                rep[j] = i;
                j = rotr(j);
            }
        }
 
    dp[0][0] = true;
    int bm = 0;
    for (int i = 1; i <= 3*n; i++) {
        bm ^= 1 << (i-1) % n;           // effect of a switch in round i
        for (int b = 0; b < (1 << n); b++)
            if (dp[i-1][rep[b]])
                dp[i][rep[b ^ bm]] = true;
    }
 
    for (int i = 0; i < T; i++) {       // answer queries
        char sa[25], sb[25];
        scanf("%s %s", sa, sb);
        int li = parse(sa), sw = parse(sb);
        for (int j = 0; j < 3*n; j++) {
            if (dp[j][rep[li]]) {
                printf("%d\n", j);
                break;
            }
            li ^= sw;
            sw = rotr(sw);
        }
    }
    return 0;
}