题意
有一个由 \(0/1\) 组成的字符串 \(S\)。
给你 \(m\) 次操作。
假如 \(S_{u} = 1\) 且 \(S_{v} = 0\),则交换 \(S_{u}, S_{v}\)。
假如对于所有的 \(S\),使得最终字符串 \(S'\) 的所有 \(1\) 相邻。
请输出 \(1\) 的个数为 \([1, n]\) 的 \(S\) 的方案数。
答案对 \(2\) 取模。
\(n \le 35, m \le 1000\)
Sol
有一个很明显的 \(2 ^ n \times m\) 做法。
枚举 \(S\) 的最初状态,暴力操作 \(m\) 次。
套路地,考虑用 \(0, 1, 2\) 来表示当前的状态。
分类讨论。
- 若 \(S_u\) 与 \(S_v\) 都为 \(2\)。
注意到对于 \(S_u \neq S_v\) 时。
\(0\) 和 \(1\) 与 \(1\) 和 \(0\) 在操作过后都会变成 \(0\) 和 \(1\) 这个状态。
也就是说,当前的两种情况对于答案的贡献为 \(0\)。
直接不考虑即可。
只需要考虑 \(S_u = S_v = 0\) 和 \(S_u = S_v = 1\) 即可。
- 若 \(S_u\) 与 \(S_v\) 有一个为 \(2\)。
手摸一下可以发现,只要带 \(1\) 就会变成 \(2\) 和 \(1\)。
只要带 \(0\) 就会变成 \(0\) 和 \(2\)。
- 若 \(S_u\) 与 \(S_v\) 都不为 \(2\)。
两个都确定了,直接转移即可。
冷静一下。
发现状态变多的同时会使 \(2\) 的个数减 \(2\),剩下所有情况都不会使状态变多。
状态数的级别为 \(O(2 ^ {n / 2})\)。
做完了。
最后统计一个状态是否合法。
总复杂度:\(O(2 ^ {n / 2} m + 2 ^ {n / 2} n ^ 2)\)。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <bitset>
#include <vector>
#define int long long
#define il inline
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
il int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
bool _stmer;
#define fi first
#define se second
const int N = 36, M = 1005;
array <int, N> ans;
array <pii, M> s;
il void dfs(int n, int m, int isl1, int isl2, int x, int val) {
if (x > m) {
int tp0 = 0;
for (int i = 1; i <= n; i++)
if (isl1 & (1ll << (i - 1))) tp0++;
for (int i = 1; i <= n; i++) {
int tp1 = 0;
for (int j = i; j <= n; j++) {
if (!(isl1 & (1ll << (j - 1))) && !(isl2 & (1ll << (j - 1)))) break;
tp1 += (bool)(isl1 & (1ll << (j - 1)));
if (tp0 == tp1) ans[j - i + 1]++;
}
}
return;
}
int u = 1ll << (s[x].fi - 1), v = 1ll << (s[x].se - 1);
if ((isl2 & u) && (isl2 & v)) {
dfs(n, m, isl1, isl2 ^ u ^ v, x + 1, val - 2);
dfs(n, m, isl1 ^ u ^ v, isl2 ^ u ^ v, x + 1, val - 2);
}
else if (!(isl2 & u) && !(isl2 & v)) {
if ((isl1 & u) && !(isl1 & v))
isl1 ^= u, isl1 ^= v;
dfs(n, m, isl1, isl2, x + 1, val);
}
else {
if ((isl1 & u) || (isl1 & v)) {
if (isl1 & u) isl1 ^= u ^ v, isl2 ^= u ^ v;
dfs(n, m, isl1, isl2, x + 1, val);
}
else {
if (isl2 & u) isl2 ^= u ^ v;
dfs(n, m, isl1, isl2, x + 1, val);
}
}
}
bool _edmer;
signed main() {
cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
int n = read(), m = read();
for (int i = 1; i <= m; i++)
s[i].fi = read(), s[i].se = read();
dfs(n, m, 0, (1ll << n) - 1, 1, n);
for (int i = 1; i <= n; i++)
write(ans[i] % 2), putchar(32);
puts("");
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
return 0;
}
标签:状态,le,polygon,省选,T1,int,include,20240321,define
From: https://www.cnblogs.com/cxqghzj/p/18094325