P10360 [PA2024] Desant 3 - Solution
strcmp
·
·
题解
我们先令 $a_x = 1$ 代表 $x$ 准备好了，$a_x = 0$ 代表 $x$ 没有准备好。
于是考虑暴力。你考虑最基础的暴力，就是直接枚举 $2^{n}$ 种状态直接判定，复杂度 $\Theta((n + m)2^n)$，肯定炸。
这个操作仍然太过于抽象，如果是正常的求，几乎想不到任何除了暴力外的做法。
但是题目为什么要对 $2$ 取模呢？对 $2$ 取模就是一个突破口，实际上，这类对 $2$ 取模的计数题，经常是寻找方案之间的对偶性。如果我们知道 $x$ 的后继有两种可能，而且递归计算这两种后继的贡献的奇偶性一定相等（我们并不关心它们具体贡献了什么，而只关心它们的奇偶性到底相等不相等），那么我们就可以直接忽略掉这两个后继，不计算它们。毕竟它们最后对答案（对 $2$ 取模）不存在任何影响。
这确实是一种套路，没见过的人感觉是挺难想到的，我自己还是在信友队的 NOIP 模拟赛上学到这个技巧的，比如 [AGC050F](https://www.luogu.com.cn/problem/AT_agc050_f) 就是这种类型的好题。
于是考虑二进制枚举应该没什么出路了，我们考虑搜索然后根据这个性质能不能剪枝。
刚开始，我们想象整个序列都是问号，然后我们要在问号里填数。
不妨枚举每个操作，保存我们当前存在的状态。
比如现在操作要我们交换 $x,\,y$。
- $x,\,y$ 都是问号，这其实比较棘手。分开讨论，如果 $x,\,y$ 状态不同，比如我们令 $a_x = 1,\,a_y = 0$ 或者 $a_x = 0,\,a_y = 1$。发现了吗？$a_x = 1,\,a_y = 0$ 经过操作一定会变换成 $a_x = 0,\,a_y = 1$。于是我们就有了两个后继状态，它们是一模一样的，对答案显然没影响（对 $2$ 取模），所以我们可以直接忽略掉它们状态不同的可能。于是只需要钦定 $a_x,\,a_y$ 状态相同即可，枚举 $0/1$ 状态暴搜即可。
- $x,\,y$ 中只有一个问号，如果问号在 $y$ 上且 $a_x = 0$ 就忽略掉，否则 $a_x = 1$。此时考虑 $a_y$ 的取值，要么为 $0$ 要么为 $1$。如果是 $0$ 那么就交换，否则不交换。看起来产生了两个新状态，但其实是一个。我们的后继状态一定 $a_x' = a_y,\,a_y' = 1$，于是只产生了唯一的后继状态，也就是 $x$ 位置是问号且 $a_y = 1$。问号在 $x$ 上是对称的，也只有一个后继状态。
- $x,\,y$ 中没有问号，那直接根据题意交换或不交换即可。
只有第一种情况会产生多个（两个）后继。这里每次决策会恰好去掉两个问号，问号总数是 $\Theta(n)$ 的，决策只有 $\lceil\frac{n}{2}\rceil$ 级别。也就是状态数是 $2^{\lceil\frac{n}{2}\rceil}$ 级别的。
哦还有一个小细节，就是我们经过 $m$ 个操作之后可能有状态仍然包含问号。
这如何统计答案？发现这些问号我们直接钦定区间里面是 $1$ 区间外面都是 $0$ 即可，对答案没影响。
时间复杂度 $\Theta((n^2 + m)\sqrt{2^n})$，最终状态数卡满大概 $2^{17}$ 级别，可以通过。
```cpp
#include <bits/stdc++.h>
#define X first
#define Y second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long int ll;
using ull = unsigned long long int;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pq = priority_queue<int>;
using ld = double;
constexpr int maxn = 1e5 + 10, bs = 19260817, mod = 22309287;
constexpr ll inf = 1.1e14;
int a[42], n, m, l[maxn], r[maxn], ans[42];
void dfs(int u) {
if (u == m + 1) {
int cnt = 0; rep(i, 1, n) cnt += (a[i] == 1);
for (int i = 1, v = 0; i <= n; i++, v = 0) rep(j, i, n) {
if (a[j] == 0) break;
if (((v += (a[j] == 1)) == cnt)) ans[j - i + 1] ^= 1;
}
return;
}
int x = l[u], y = r[u];
if (a[x] == -1 && a[y] == -1) a[x] = a[y] = 0, dfs(u + 1), a[x] = a[y] = 1, dfs(u + 1), a[x] = a[y] = -1;
else if (a[x] == -1 || a[y] == -1) {
if (a[x] == 0 || a[y] == 1) dfs(u + 1);
else if (a[x] == 1) { a[x] = -1, a[y] = 1; dfs(u + 1); a[x] = 1, a[y] = -1; }
else if (a[y] == 0) { a[x] = 0, a[y] = -1; dfs(u + 1); a[x] = -1, a[y] = 0; }
}
else {
if (a[x] == 1 && a[y] == 0) a[x] = 0, a[y] = 1, dfs(u + 1), a[x] = 1, a[y] = 0;
else dfs(u + 1);
}
}
int main() {
scanf("%d%d", &n, &m);
rep(i, 1, m) scanf("%d%d", &l[i], &r[i]);
memset(a, -1, sizeof(a)); dfs(1);
rep(i, 1, n) printf("%d ", ans[i]);
return 0;
}
```