260226 杂题选讲
考虑如果有两张 \(2^k\)，那么显然可以调整成 \(2^k,2^{k+1}\)；如果有一张 \(2^k\) 一张 \(2^{-k}\)，那么可以调整成 \(2^{k+1}\) 和 \(2^{-k}\)。
然后考虑搜索，先考虑 \(2^0\)，如果所有数都是偶数那么显然不用选，直接除以 \(2\) 递归；否则枚举两张卡，然后把所有奇数减去，然后除以 \(2\) 递归；时间复杂度 \(T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)\)。
首先对原问题进行转置，转化为任意路径颜色数不超过 \(k\) 时最多填多少种颜色。需要通过手玩得到 \(k\) 比较小的时候的规律然后直接推广即可。
每次把彩灯一端移动到最深的位置，然后再移动另一端，如此反复。最终彩灯要么卡在某个角落里，可以描述为一条链 \((a,b)\) 满足 \(a\) 向外延伸的最长长度加 \(dis(a,b)\) 等于 \(k\)，\(b\) 向外延伸的最长长度加 \(dis(a,b)\) 也等于 \(k\)，随后容易证明如果两个 \((a,b)\) 不等，那么它们不能相互到达。要么彩灯自由了（不存在上面的链 \((a,b)\)），此时彩灯一定可以走到直径上。
第一种情况用启发式合并做一下就行。第二种情况判一下 \(+1\)。
考虑把 \(n\) 个二进制数按顺序拼接起来，然后对这些长为 \(nk\) 的 01 向量求线性基。但直接做显然是 \(O(2^k)\) 的。考虑只保留一些有用的向量，考察 \((a_i+x)\oplus(a_i+x-2^k)\)，其中 \(2^k\) 是 \(x\) 的最高位。发现分讨 \(a_i+x\) 的低 \(k\) 位是否向高位进位，容易知道这玩意只有两个取值：\((a_i+2^k)\oplus a_i\) 和 \((a_i+2^{k+1})\oplus (a_i+2^k)\)。根据单调性可知固定一个 \(k\) 之后这个向量只有 \(O(n)\) 种本质不同的取值。还要额外插入 \(x=0\) 时的向量，不难说明通过这些向量可以组合出所有向量。
时间复杂度 \(O(\frac{(nk)^3}{w})\)。
代码
| #include<iostream>
#include<bitset>
#include<cassert>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
typedef bitset<4096> bs;
const int N = 55;
int n, k; ull mod;
ull a[N], c[N], tmp[N];
inline bs merge(ull arr[]) {
bs res;
for(int i = 0; i < n; i++)
for(int j = 0; j < k; j++)
res.set(i * k + j, (arr[i] >> j & 1));
return res;
}
bs lb[4096], res[4096]; ull val[4096]; int nn;
inline void insert(bs v, ull x) {
bs r;
for(int i = n * k - 1; i >= 0; i--) {
if(!v.test(i)) continue;
if(!lb[i].any()) return lb[i] = v, r.set(nn), val[nn++] = x, res[i] = r, void();
else v ^= lb[i], r ^= res[i];
}
}
unordered_map<ull, bool> mp;
vector<ull> ans;
int main() {
cin >> n >> k; mod = (1ull << k) - 1;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++) cin >> c[i];
insert(merge(a), 0);
for(int kk = 0; kk < k; kk++) {
ull num[N]; int nn;
ull mask = (1ull << kk); nn = 0; num[++nn] = 0;
for(int i = 0; i < n; i++) if(a[i] & mask - 1) num[++nn] = mask - (a[i] & mask - 1);
sort(num + 1, num + 1 + nn); nn = unique(num + 1, num + 1 + nn) - (num + 1);
for(int i = 1; i <= nn; i++) {
ull x = num[i]; assert((x >> kk) == 0);
for(int j = 0; j < n; j++) tmp[j] = ((a[j] + x + (1ull << kk)) & mod) ^ ((a[j] + x) & mod);
insert(merge(tmp), x + (1ull << kk));
}
}
bs C = merge(c), r;
for(int i = n * k - 1; i >= 0; i--) {
if(C.test(i)) {
if(!lb[i].any()) { cout << "-1\n"; return 0; }
C ^= lb[i]; r ^= res[i];
}
}
for(int i = 0; i < nn; i++) {
if(r.test(i)) {
mp[val[i]] ^= 1;
if(val[i]) mp[val[i] - (1ull << __lg(val[i]))] ^= 1;
}
}
for(auto [val, w] : mp) if(w) ans.push_back(val);
cout << ans.size() << '\n';
for(ull i : ans) cout << i << ' '; cout << '\n';
return 0;
}
|
首先需要观察到一些基本性质：若 \((x,y)\) 之间有边，\(z\) 不是孤立点，那么有构造 xyz -> zwz -> zxy，即边可以随便跑。若 \((p,q),(x,y),(y,z)\) 之间都有边，那么 pqz -> xyz -> xyx -> pqx，即借助自由边我们可以让任意一个点在图上走两步。
于是先找出所有孤立点，把序列划分成若干段。然后判断序列初始就没有边的情况，此时动不了。然后我们把其中一个序列拿过来，维护一个栈，然后一个一个插入，如果和栈顶匹配成了一条边，那么它们就自由了，将它们扔旁边。最后会剩一堆匹配不成边的点，容易说明这些点和自由边进行操作只会等价于在图上走两步，不会走出等价类。因此直接比较栈里剩下的东西是不是完全一样即可。
观察到一个充要条件是对于每个不在 \(S\) 中的点，存在一个 \(S\) 中的点满足两者有边并且后者比前者先加进去。注意到存在的限制不好做，考虑把它容斥成 forall 的限制。发现我们可以枚举 \([1,m]\setminus S\) 的一个子集 \(T\) 并钦定 \(T\) 不满足限制，\([1,m]\setminus S\) 中的其它元素任意，\((m,n]\) 中的元素仍然满足限制（只有 uoj 才会出这么神秘的分类讨论吧）。不满足限制即所有 \(S\) 中的和它有连边的都在它后面。
于是我们尝试确定 \(T+(S\cap [1,m])\) 在 \(p\) 中的一个顺序，此时其内部就已经有一些 \(T\) 和 \(S\) 的限制了。然后考虑把 \((m,n]\) 的东西插入进去，对于 \(u\in (m,n]\cap S\)，它显然应该在 \(T\) 中最后一个和它有连边的元素后面；对于 \(u\in (m,n]\setminus S\)，显然它只有来自于 \([1,m]\cap S\) 的限制，它应该在 \(S\cap [1,m]\) 中第一个和它有连边的元素后面。然后形如一个树的拓扑序计数，我们需要对每个序列的后缀知道必须排在它里面的 \((m,n]\) 的元素的数量，这玩意可以用一些 fmt 预处理出来。
然后状压 dp，从后往前确定这个顺序（显然正着没法做），然后容斥即可。
代码
| #include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int M = 20;
const int MOD = 998244353;
inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }
inline int mod(int a) { return (a >= MOD) ? a - MOD : a; }
int n, m, ans;
int a[N], ss;
bool s[N];
int w[1 << M], f[1 << M];
int inv[N];
int main() {
inv[1] = 1;
for(int i = 2; i < N; i++) inv[i] = MOD - (ll)inv[MOD % i] * (MOD / i) % MOD;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) { char c; cin >> c; s[i] = (c == '1'); }
for(int i = 1; i <= n; i++)
if(s[i])
for(int j = 1; j <= m; j++)
if(s[j] && (a[i] >> j - 1 & 1)) cout << 0 << '\n', exit(0);
for(int i = 1; i <= m; i++) ss |= s[i] * (1 << i - 1);
for(int i = m + 1; i <= n; i++)
if(!s[i] && (a[i] & ss) == 0) cout << 0 << '\n', exit(0);
for(int i = m + 1; i <= n; i++)
if(s[i]) w[a[i] & ~ss]++;
for(int k = 0; k < m; k++)
for(int i = 0; i < (1 << m); i++)
if(i >> k & 1) add(w[i ^ (1 << k)], w[i]);
w[0] = 0;
for(int i = 0; i < (1 << m); i++)
w[i] = __builtin_parity(i) ? w[i] : mod(MOD - w[i]);
for(int i = m + 1; i <= n; i++)
if(!s[i]) w[a[i] & ss]++;
for(int k = 0; k < m; k++)
for(int i = 0; i < (1 << m); i++)
if(i >> k & 1) add(w[i], w[i ^ (1 << k)]);
f[0] = 1;
for(int t = 1; t < (1 << m); t++)
for(int i = 0; i < m; i++)
if(t >> i & 1 && !((ss >> i & 1) && (a[i + 1] & ~ss & t)))
add(f[t], (ll)f[t ^ (1 << i)] * inv[w[t] + __builtin_popcount(t)] % MOD);
for(int t = 0; t < (1 << m); t++) {
if((ss & t) != ss) continue;
if(__builtin_parity(t ^ ss)) add(ans, MOD - (ll)f[t]);
else add(ans, (ll)f[t]);
}
cout << ans << '\n';
return 0;
}
|