T1
NFLSOJ P3581 No more xor problems, please!
实际上是异或和是最小公倍数的倍数。我们知道异或的结果二进制位数小于等于原来的。如果两个数没有倍数关系，则其最小公倍数一定不整除其异或和，因为最小公倍数的二进制位数至少多 \(1\)。所以合法的子集要么异或和为 \(0\)，要么一个数是别的所有数的倍数，然后别的数的异或和为 \(0\)。求子集异或和为 \(0\) 的方案数可以使用线性基，设有 \(k\) 个数没有成功插入线性基，则答案就是 \(2^{k} - 1\)，\(-1\) 是减去空集。因此我们把每个数的因子都拎出来扔到线性基里面，就可以算这个数为最大公约数时的答案。还有一些别的细节，都在代码里。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 998244353;
inline char nc(){
static char buf[1000005],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000005,stdin),p1==p2)?EOF:*p1++;
}
inline int read() {
int ret = 0;
char c = nc();
while (c < '0' || c > '9') c =nc();
while ('0' <= c && c <= '9') ret = ret * 10 + c - 48, c = nc();
return ret;
}
int n;
int a[1000005];
struct XOR_Linear_Base {
int p[20], unsec;
void Insert(int x) {
for (int i = 19; ~i; i--) {
if (x & (1 << i)) {
if (p[i])
x ^= p[i];
else {
p[i] = x;
return;
}
}
}
++unsec;
}
} p[1000005];
int qpow(int x, int y) {
int ret = 1;
while (y) {
if (y & 1)
ret = ret * x % P;
y >>= 1;
x = x * x % P;
}
return ret;
}
int ap[1000005];
int ans = 1;
int fac[1000005], ifac[1000005], inv[1000005];
void Cpre(int n) {
fac[1] = ifac[1] = inv[1] = fac[0] = ifac[0] = inv[0] = 1;
for (int i = 2; i <= n; i++) {
fac[i] = fac[i - 1] * i % P;
inv[i] = (P - P / i) * inv[P % i] % P;
ifac[i] = ifac[i - 1] * inv[i] % P;
}
}
int C(int n, int m) { return (n < 0 || m < 0 || n < m ? 0 : (fac[n] * ifac[m] % P * ifac[n - m] % P)); }
signed main() {
freopen("xor.in", "r", stdin);
freopen("xor.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
ap[a[i]]++;
p[0].Insert(a[i]);
}
Cpre(n);
ans = qpow(2, p[0].unsec);
for (int i = 1; i <= n; i++) {
if (ap[i]) {
for (int j = 1; j <= ap[i]; j += 2) {
ans += C(ap[i], j) * qpow(2, p[i].unsec) % P;
ans >= P ? (ans -= P) : 0;
}
for (int j = 1; i * j <= n; j++) {
if (ap[i * j]) {
for (int asdf = 1; asdf <= ap[i]; asdf++)
p[i * j].Insert(i);
}
}
}
}
cout << (ans + P - 1) % P << "\n";
return 0;
}
T2
NFLSOJ P3580 Link Cut Tree
从叶子往上贪，设 \(f[i][0 / 1]\) 表示以 \(i\) 为根的子树，当前最上面一个连通块权值和为偶数 / 奇数时的最大块数，\(g[i][0 / 1]\) 表示最大块数时最上面一个连通块的权值最大多少。把儿子都转移过来之后如果奇偶性与 \(k\) 相同的那个权值可以消，就消掉。这样就是最优的。
代码
#include <iostream>
#define int long long
using namespace std;
const int inf = 214748647;
int n, k;
int head[1000005], nxt[2000005], to[2000005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
pair<int, int> f[1000005][2];
int a[1000005];
pair<int, int> operator+(pair<int, int> a, pair<int, int> b) { return make_pair(a.first + b.first, a.second + b.second); }
void dfs(int x, int fa) {
for (int i = head[x]; i; i = nxt[i]) to[i] != fa ? dfs(to[i], x) : void();
pair<int, int> tmp[2];
tmp[0] = tmp[1] = f[x][0] = f[x][1] = make_pair(-inf, -inf);
tmp[a[x] & 1] = make_pair(0, a[x]);
int s = 0;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa) {
s += max(f[v][0].first, f[v][1].first);
pair<int, int> x[2];
x[0] = tmp[0], x[1] = tmp[1];
tmp[0] = max(x[0] + f[v][0], x[1] + f[v][1]);
tmp[1] = max(x[0] + f[v][1], x[1] + f[v][0]);
}
}
tmp[0] = max(tmp[0], make_pair(s, 0ll));
for (int i = 0; i < 2; i++) {
f[x][i] = max(f[x][i], tmp[i]);
if ((i == (k & 1)) && tmp[i].second >= k)
f[x][0] = max(f[x][0], make_pair(tmp[i].first + 1, 0ll));
}
}
signed main() {
freopen("linkcut.in", "r", stdin);
freopen("linkcut.out", "w", stdout);
int tc;
cin >> tc;
while (tc--) {
cin >> n >> k;
for (int i = 1; i <= n; i++) head[i] = 0, cin >> a[i];
ecnt = 0;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1, 0);
cout << max(f[1][0].first, f[1][1].first) << "\n";
}
return 0;
}
T3
NFLSOJ P12666 矩形
考虑容斥。拿总方案数减去不合法的。不合法的就是和为 \(3, 2, 1\)。和为 \(2, 1\) 时可以发现其中必有恰好两个点向外连一条 \(0\) 和一条 \(1\)。所以设每个点度数为 \(deg_i\)，则这两种的总方案数就是 \(\frac{1}{2}\sum deg_i(n - 1 - deg_i)\)。求 \(deg\) 就考虑每个点有多少矩形与它不交。可以发现不交肯定是在左边或上面或右边或下面，或者在四个角上。先算出前四种的和，然后减去后四个角上的情况。接下来考虑和为 \(3\) 的情况。考虑扫描线，对每个三元组在其中最晚加入的矩形处算贡献。相当于一堆区间 \([l_i, r_i]\)，问你有多少个二元组使得这个二元组中的区间都和给定区间 \([L, R]\) 有交且这两个区间有交。首先去掉与 \([L, R]\) 无交的，然后考虑拿总的减去这两个区间无交的，也就是 \(r_i < l_j\) 的 \(i, j\) 个数。开权值线段树维护左右端点，相当于求 \(\sum_{L \le i, j \le R} cntr_i \times cntl_j\)。这个东西类似于归并地做就可以了，应该是容易的。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
#define int long long
#define lowbit(x) ((x) & (-(x)))
using namespace std;
int n;
struct Rectangular {
int l, r, d, u, deg;
} a[2000005];
struct BIT {
int bit[4000005];
void add(int x, int y) { for (; x <= 4000000; x += lowbit(x)) bit[x] += y; }
int query(int x) {
int ret = 0;
for (; x; x -= lowbit(x)) ret += bit[x];
return ret;
}
void clear() { memset(bit, 0, sizeof bit); }
} bit, bit2;
map<int, int> mp[2];
int d[2][2000005];
vector<int> vecl[4000005], vecr[4000005], vecd[4000005], vecu[4000005];
struct node {
int cntl, cntr, val;
} T[4000005];
node operator+(node a, node b) {
node c;
c.cntl = a.cntl + b.cntl;
c.cntr = a.cntr + b.cntr;
c.val = a.val + b.val + a.cntr * b.cntl;
return c;
}
struct Segment_Tree {
void AddL(int o, int l, int r, int x, int v) {
if (l == r) {
T[o].cntl += v;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
AddL(o << 1, l, mid, x, v);
else
AddL(o << 1 | 1, mid + 1, r, x, v);
T[o] = T[o << 1] + T[o << 1 | 1];
}
void AddR(int o, int l, int r, int x, int y) {
if (l == r) {
T[o].cntr += y;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
AddR(o << 1, l, mid, x, y);
else
AddR(o << 1 | 1, mid + 1, r, x, y);
T[o] = T[o << 1] + T[o << 1 | 1];
}
node Query(int o, int l, int r, int L, int R) {
if (L <= l && r <= R)
return T[o];
int mid = (l + r) >> 1;
if (R <= mid)
return Query(o << 1, l, mid, L, R);
if (L > mid)
return Query(o << 1 | 1, mid + 1, r, L, R);
return Query(o << 1, l, mid, L, R) + Query(o << 1 | 1, mid + 1, r, L, R);
}
} seg;
signed main() {
freopen("rect.in", "r", stdin);
freopen("rect.out", "w", stdout);
cin >> n;
cin >> a[1].l;
for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r >> a[i].d >> a[i].u, d[0][++d[0][0]] = a[i].l, d[0][++d[0][0]] = a[i].r, d[1][++d[1][0]] = a[i].d, d[1][++d[1][0]] = a[i].u;
sort(d[0] + 1, d[0] + d[0][0] + 1);
sort(d[1] + 1, d[1] + d[1][0] + 1);
for (int i = 1; i <= n * 2; i++) mp[0][d[0][i]] = (mp[0][d[0][i - 1]] + (d[0][i] != d[0][i - 1])), mp[1][d[1][i]] = (mp[1][d[1][i - 1]] + (d[1][i] != d[1][i - 1]));
int X = mp[0][d[0][n * 2]], Y = mp[1][d[1][n * 2]];
for (int i = 1; i <= n; i++) {
vecl[a[i].l = mp[0][a[i].l]].emplace_back(i);
vecr[a[i].r = mp[0][a[i].r]].emplace_back(i);
vecd[a[i].d = mp[1][a[i].d]].emplace_back(i);
vecu[a[i].u = mp[1][a[i].u]].emplace_back(i);
}
int cnt = 0;
for (int i = 1; i <= X; i++) {
for (auto v : vecl[i]) a[v].deg += cnt;
cnt += vecr[i].size();
}
cnt = 0;
for (int i = X; i; i--) {
for (auto v : vecr[i]) a[v].deg += cnt;
cnt += vecl[i].size();
}
cnt = 0;
for (int i = 1; i <= Y; i++) {
for (auto v : vecd[i]) a[v].deg += cnt;
cnt += vecu[i].size();
}
cnt = 0;
for (int i = Y; i; --i) {
for (auto v : vecu[i]) a[v].deg += cnt;
cnt += vecd[i].size();
}
for (int i = 1; i <= X; i++) {
for (auto v : vecl[i]) a[v].deg -= (bit.query(Y) - bit.query(a[v].u));
for (auto v : vecr[i]) bit.add(a[v].d, 1);
}
bit.clear();
for (int i = X; i; i--) {
for (auto v : vecr[i]) a[v].deg -= bit.query(a[v].d - 1);
for (auto v : vecl[i]) bit.add(a[v].u, 1);
}
bit.clear();
for (int i = 1; i <= X; i++) {
for (auto v : vecl[i]) a[v].deg -= bit.query(a[v].d - 1);
for (auto v : vecr[i]) bit.add(a[v].u, 1);
}
bit.clear();
for (int i = X; i; i--) {
for (auto v : vecr[i]) a[v].deg -= (bit.query(Y) - bit.query(a[v].u));
for (auto v : vecl[i]) bit.add(a[v].d, 1);
}
bit.clear();
int ans1 = 0;
for (int i = 1; i <= n; i++) ans1 += a[i].deg * (n - 1 - a[i].deg);
ans1 /= 2;
int icnt = 0;
int ans2 = 0;
for (int i = 1; i <= X; i++) {
for (auto v : vecl[i]) {
int tmp = icnt - bit.query(a[v].d - 1) - (bit2.query(Y) - bit2.query(a[v].u));
ans2 += tmp * (tmp - 1) / 2 - seg.Query(1, 1, Y, a[v].d, a[v].u).val;
bit.add(a[v].u, 1), bit2.add(a[v].d, 1);
seg.AddL(1, 1, Y, a[v].d, 1), seg.AddR(1, 1, Y, a[v].u, 1);
++icnt;
}
for (auto v : vecr[i]) {
--icnt;
bit.add(a[v].u, -1), bit2.add(a[v].d, -1);
seg.AddL(1, 1, Y, a[v].d, -1), seg.AddR(1, 1, Y, a[v].u, -1);
}
}
cout << n * (n - 1) * (n - 2) / 6 - ans1 - ans2 << "\n";
return 0;
}
</details>
---
线性基求子集异或和为 $0$ 的方案数。
大力容斥，分讨。