20250929
T1
制作美食
注意到只有 \(a\) 的前綴最大值是有用的，其他東西要么孤立要么和之前的前綴最大值連通。然后只需要對每個 \(b\) 找到連的是哪個區間，并查集合并一下即可。當然也可能孤立，就直接貢獻答案。
代碼
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
#define lowbit(x) ((x) & (-(x)))
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++
char buf[1<<21], *p1, *p2, ch;
long long read() {
long long ret = 0, neg = 0; char c = getchar(); neg = (c == '-');
while (c < '0' || c > '9') c = getchar(), neg |= (c == '-');
while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
return ret * (neg ? -1 : 1);
}
int n, m;
int a[2000005], b[2000005];
struct BIT {
int bit[2000005];
void add(int x, int y) { for (; x <= n; x += lowbit(x)) bit[x] += y; }
int query(int x) {
int ret = 0;
for (; x; x -= lowbit(x)) ret += bit[x];
return ret;
}
} bit;
int o[2000005];
int p[2000005], pcnt;
int q[2000005], qcnt;
int ans;
int stk[2000005], sz;
int dsu[2000005];
int getf(int x) { return dsu[x] == x ? x : (dsu[x] = getf(dsu[x])); }
int main() {
freopen("delidish.in", "r", stdin);
freopen("delidish.out", "w", stdout);
int tc = read();
while (tc--) {
ans = pcnt = qcnt = sz = 0;
n = read(), m = read();
for (int i = 1; i <= n; i++) a[i] = read(), o[i] = i, dsu[i] = i, bit.bit[i] = 0;
for (int i = 1; i <= m; i++) b[i] = read();
sort(o + 1, o + n + 1, [](int x, int y) { return a[x] < a[y]; });
for (int i = 1, j = 1; i <= n; i++) {
while (j <= m && j <= a[o[i]]) bit.add(n - b[j] + 1, 1), ++j;
if (bit.query(n - o[i] + 1)) p[++pcnt] = o[i];
else ++ans;
}
sort(p + 1, p + pcnt + 1);
for (int i = 1, mx = 0; i <= pcnt; i++) if (a[p[i]] > mx) q[++qcnt] = p[i], mx = a[p[i]];
dsu[pcnt] = pcnt;
for (int i = 1, j = 1; i <= m; i++) {
while (j <= qcnt && i > a[q[j]]) ++j;
int t = upper_bound(q + 1, q + qcnt + 1, b[i]) - q - 1;
if (j <= t) for (int x = getf(j); x < t; x = getf(x)) dsu[x] = x + 1;
else ++ans;
}
for (int i = 1; i <= qcnt; i++) ans += (getf(i) == i);
cout << ans << "\n";
}
return 0;
}
T2
樹與排列
\(f_{i, j}\) 表示 \(i\) 子樹，分成了 \(j\) 個連續段的 \(\sum\prod\)。把子樹拼起來之后可以欽定一些子樹的連續段進行合并并乘上自己深度的貢獻。但是不能合并相同子樹的連續段。
-
因此對非法合并容斥。加入一棵子樹時在子樹里欽定一些非法合并然后乘容斥系數求和即可。這樣每個出現了非法合并的方案的每個非法合并的子集都被乘了容斥系數求和，因此貢獻為 \(0\)。而沒有非法合并的貢獻就是 \(1\)。那么做完了。
-
考慮將乘積拆開，即為在每個 LCA 的到根鏈上選一個點的方案數。那么發現這樣我們就可以合并相同子樹的連續段了，只是不必再乘上自己深度的貢獻。那么直接做就好了。
代碼（容斥）
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
const int P = 1000000007;
inline void Madd(int &x, int y) { (x += y) >= P ? (x -= P) : 0; }
inline int Msum(int x, int y) { return Madd(x, y), x; }
int n;
int head[505], nxt[505], to[505], ecnt;
inline void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int C[505][505];
int f[505][505], tmp[505];
int sz[505], fa[505];
int pw[505][505];
void dfs(int x, int d) {
f[x][sz[x] = 1] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
dfs(v, d + 1);
memset(tmp, 0, sizeof tmp);
for (int a = 1; a <= sz[v]; a++) {
for (int b = a + 1; b <= sz[v]; b++) {
if ((b - a) & 1) Madd(f[v][a], P - f[v][b] * C[b - 1][b - a] % P * pw[d][b - a] % P);
else Madd(f[v][a], f[v][b] * C[b - 1][b - a] % P * pw[d][b - a] % P);
}
}
for (int a = 1; a <= sz[x]; a++) {
for (int b = 1; b <= sz[v]; b++)
Madd(tmp[a + b], f[x][a] * f[v][b] % P * C[a + b][b] % P);
}
sz[x] += sz[v];
memcpy(f[x], tmp, sizeof tmp);
}
for (int i = 1; i <= sz[x]; i++) {
for (int j = i + 1; j <= sz[x]; j++)
Madd(f[x][i], f[x][j] * C[j - 1][j - i] % P * pw[d][j - i] % P);
}
}
signed main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
cin >> n;
for (int i = C[0][0] = 1; i <= n; i++) {
for (int j = C[i][0] = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
for (int j = pw[i][0] = 1; j <= n; j++) pw[i][j] = pw[i][j - 1] * i % P;
}
for (int i = 2; i <= n; i++) cin >> fa[i], add(fa[i], i);
dfs(1, 1);
cout << f[1][1] << "\n";
return 0;
}
代碼（product trick）
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
const int P = 1000000007;
inline void Madd(int &x, int y) { (x += y) >= P ? (x -= P) : 0; }
inline int Msum(int x, int y) { return Madd(x, y), x; }
int n;
int head[505], nxt[505], to[505], ecnt;
inline void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int C[505][505];
int f[505][505], tmp[505];
int sz[505], fa[505];
int pw[505][505];
void dfs(int x, int d) {
f[x][sz[x] = 1] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
dfs(v, d + 1);
memset(tmp, 0, sizeof tmp);
for (int a = 1; a <= sz[x]; a++) {
for (int b = 1; b <= sz[v]; b++)
Madd(tmp[a + b], f[x][a] * f[v][b] % P * C[a + b][b] % P);
}
sz[x] += sz[v];
memcpy(f[x], tmp, sizeof tmp);
}
for (int i = 1; i <= sz[x]; i++) {
for (int j = i + 1; j <= sz[x]; j++)
Madd(f[x][i], f[x][j] * C[j - 1][j - i] % P);
}
}
signed main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
cin >> n;
for (int i = C[0][0] = 1; i <= n; i++) {
for (int j = C[i][0] = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
for (int j = pw[i][0] = 1; j <= n; j++) pw[i][j] = pw[i][j - 1] * i % P;
}
for (int i = 2; i <= n; i++) cin >> fa[i], add(fa[i], i);
dfs(1, 1);
cout << f[1][1] << "\n";
return 0;
}
T3
樹上區域顏色并
考慮如何對子樹數顏色，只需要對子樹每個顏色維護出現的最淺深度。然后開一個線段樹維護這個最淺深度的計數數組，以支持單點修改區間求和。那么離線做完了。在線考慮直接把 dsu on tree 對桶的所有修改可持久化下來就好了。由于強制在線不完全，可以在每個詢問的時候知道我們到底想要哪些顏色的最淺深度，于是最淺深度的那個數組不需要可持久化。那么就做完了，空間 \(\mathcal{O}(m \log^2 m)\)，時間 \(\mathcal{O}(nq + q \log m + m \log^2 m)\)。
代碼
#include <iostream>
#include <string.h>
#include <vector>
#include <array>
#include <set>
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++
char buf[1<<21], *p1, *p2, ch;
long long read() {
long long ret = 0, neg = 0; char c = getchar(); neg = (c == '-');
while (c < '0' || c > '9') c = getchar(), neg |= (c == '-');
while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
return ret * (neg ? -1 : 1);
}
int n, m, q;
vector<int> G1[200005], G2[200005];
int v1[25], v2[200005];
int rec[25];
array<int, 21> _clrcnt[1000005];
vector<int> vec[200005];
array<int, 5> qs[1000005];
int dfn[200005], _dfn[200005], ncnt;
int sz[200005], son[200005], fa[200005];
int dep[200005];
void dfs1(int x, int _f) {
dep[x] = dep[_f] + 1;
sz[x] = 1; fa[x] = _f;
_dfn[dfn[x] = ++ncnt] = x;
for (int v : G2[x]) {
if (v != _f) {
dfs1(v, x);
sz[x] += sz[v];
if (sz[v] > sz[son[x]]) son[x] = v;
}
}
}
int rt[200005];
struct node { int l, r, s; } T[86000005];
struct Segment_Tree {
int ncnt;
void Insert(int &p, int q, int l, int r, int x, int y) {
T[p = ++ncnt] = T[q]; T[p].s += y;
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) Insert(T[p].l, T[q].l, l, mid, x, y);
else Insert(T[p].r, T[q].r, mid + 1, r, x, y);
}
int Query(int o, int l, int r, int L, int R) {
if (!o) return 0;
if (L <= l && r <= R) return T[o].s;
int mid = (l + r) >> 1;
if (R <= mid) return Query(T[o].l, l, mid, L, R);
if (L > mid) return Query(T[o].r, mid + 1, r, L, R);
return Query(T[o].l, l, mid, L, R) + Query(T[o].r, mid + 1, r, L, R);
}
} seg;
multiset<int> st[200005];
int crt;
int mind[100005];
void _add(int x, int y) {
seg.Insert(crt, crt, 1, m + 1, mind[v2[x]], -1);
if (y == -1) st[v2[x]].erase(st[v2[x]].find(dep[x]));
else st[v2[x]].insert(dep[x]);
mind[v2[x]] = *st[v2[x]].begin(); // m + 1
seg.Insert(crt, crt, 1, m + 1, mind[v2[x]], 1);
}
void add(int x, int y) { for (int i = dfn[x]; i < dfn[x] + sz[x]; i++) _add(_dfn[i], y); }
void dfs2(int x) {
for (int v : G2[x]) if (v != fa[x] && v != son[x]) dfs2(v), add(v, -1);
if (son[x]) dfs2(son[x]);
for (int v : G2[x]) if (v != fa[x] && v != son[x]) add(v, 1);
_add(x, 1);
rt[x] = crt;
for (auto v : vec[x]) for (int i = 1; i <= n; i++) _clrcnt[v][i] = mind[_clrcnt[v][i]];
}
int _dep2[25], L[25], R[25], _ncnt;
void _dfs(int x, int fa) {
_dep2[x] = _dep2[fa] + 1; L[x] = ++_ncnt;
for (int v : G1[x]) if (v != fa) _dfs(v, x);
R[x] = _ncnt;
}
bool ap[100005];
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
n = read(), m = read(), q = read();
for (int i = 1; i < n; i++) {
int u = read(), v = read();
G1[u].emplace_back(v);
G1[v].emplace_back(u);
}
for (int i = 1; i < m; i++) {
int u = read(), v = read();
G2[u].emplace_back(v);
G2[v].emplace_back(u);
}
for (int i = 1; i <= 100000; i++) st[i].insert(m + 1), mind[i] = m + 1;
for (int i = 1; i <= n; i++) v1[i] = read(), rec[i] = v1[i];
for (int i = 1; i <= m; i++) v2[i] = read();
for (int i = 1; i <= q; i++) {
qs[i][0] = read();
if (qs[i][0] == 1) {
qs[i][1] = read(), qs[i][2] = read(), qs[i][3] = read(), qs[i][4] = read();
for (int j = 1; j <= n; j++) _clrcnt[i][j] = v1[j];
vec[qs[i][2]].emplace_back(i);
} else {
qs[i][1] = read(), qs[i][2] = read();
v1[qs[i][1]] = qs[i][2];
}
}
dfs1(1, 0);
dfs2(1);
_dfs(1, 0);
memcpy(v1, rec, sizeof rec);
int lst = 0;
for (int i = 1; i <= q; i++) {
if (qs[i][0] == 1) {
int x = qs[i][1], y = qs[i][2], a = qs[i][3] ^ lst, b = qs[i][4] ^ lst;
int ans = seg.Query(rt[y], 1, m + 1, dep[y], min(m, dep[y] + b));
for (int j = 1; j <= n; j++) if (L[x] <= L[j] && L[j] <= R[x] && _dep2[j] - _dep2[x] <= a) {
if (_clrcnt[i][j] > min(m, dep[y] + b)) {
ans += !ap[v1[j]];
ap[v1[j]] = 1;
}
}
cout << (lst = ans) << "\n";
for (int j = 1; j <= n; j++) ap[v1[j]] = 0;
} else v1[qs[i][1]] = qs[i][2];
}
return 0;
}
T4
序排速快
由于 partition 之后遞歸再 bubble 和直接 bubble 沒有區別，因此只需要考慮 bubble 的總長度。對于每個位置算貢獻。對于位置 \(i\)，將 \(<i\) 的設為 \(0\)，\(i\) 設為 \(1\)，\(>i\) 的設為 \(2\)，那么如果 \(0\) 和 \(1\) 出現的最大位置為 \(p\)，則這個位置總共會貢獻 \(p - i\) 次。當然如果 \(1\) 不在所有 \(0\) 的后面，則會有額外一次貢獻來把 \(1\) 扔到最后。那么用所有貢獻 \(p - i + 1\) 的方案減掉貢獻 \(p - i\) 的方案，列出式子：
\(\sum\limits_{i = 1}^n\sum\limits_{j = i}^ni!(n - i)!\binom{j - 1}{i - 1}(j - i + 1) - \sum\limits_{i = 1}^n\sum\limits_{j = i}^n(i - 1)!(n - i)!\binom{j - 1}{i - 1}\)。前后分別處理：
\[\begin{equation}\begin{split}
\sum\limits_{i = 1}^n\sum\limits_{j = i}^n(i - 1)!(n - i)!\binom{j - 1}{i - 1} &=
\sum\limits_{i = 1}^n(i - 1)!(n - i)!\sum\limits_{j = i}^n\binom{j - 1}{i - 1} \\
&= \sum\limits_{i = 1}^n(i - 1)!(n - i)!\binom{n}{i} \\
&= \sum\limits_{i = 1}^nn!/i \\&= n!\sum\limits_{i = 1}^n\frac1{i}
\\
\sum\limits_{i = 1}^n\sum\limits_{j = i}^ni!(n - i)!\binom{j - 1}{i - 1}(j - i + 1)
&= \sum\limits_{i = 1}^ni!(n - i)!\sum\limits_{j = i}^n\binom{j - 1}{i - 1}j - \sum\limits_{j = i}^ni!(n - i)!\binom{j - 1}{i - 1}(i - 1) \\
&= \sum\limits_{i = 1}^ni!(n - i)!\sum\limits_{j = i}^n\binom{j - 1}{i - 1}j - i!(n - i)!(i - 1)\binom{n}{i} \\
&= \sum\limits_{i = 1}^ni!(n - i)!\sum\limits_{j = i}^n\binom{j - 1}{i - 1}j - n!(i - 1) \\
&= \sum\limits_{i = 1}^ni!(n - i)!(i\binom{n}{i} + (n - i + 1)\binom{n}{i} - \binom{n + 1}{i + 1}) - n!(i - 1) \\
&= \sum\limits_{i = 1}^n(n + 1)! - (n + 1)!/(i + 1) - n!(i - 1) \\
&= n(n + 1)! - \frac{n!n(n - 1)}{2} - (n + 1)!\sum\limits_{i = 1}^n\frac1{i + 1} \\
\end{split}\end{equation}
\]
那么預處理倒數和，即可 \(\mathcal{O}(1)\) 求出一個 \(n\) 的答案。那么就做完了。
代碼
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#define int long long
using namespace std;
const int P = 998244353, i2 = (P + 1) / 2;
int fac[10000005], pi[10000005], inv[10000005];
void pre(int n) {
fac[0] = fac[1] = pi[1] = inv[0] = inv[1] = 1;
for (int i = 2; i <= n; i++) {
fac[i] = fac[i - 1] * i % P;
inv[i] = (P - P / i) * inv[P % i] % P;
pi[i] = (pi[i - 1] + inv[i]) % P;
}
}
int L, R;
signed main() {
freopen("tros.in", "r", stdin);
freopen("tros.out", "w", stdout);
cin >> L >> R;
pre(R + 2);
int ans = 0;
for (int i = L; i <= R; i++) {
int tmp = (i * fac[i + 1] % P + P - fac[i] * i % P * (i - 1) % P * i2 % P + P - fac[i] * pi[i] % P + P - fac[i + 1] * (pi[i + 1] - 1) % P) % P;
ans ^= tmp;
}
cout << ans << "\n";
return 0;
}
T2，對非法限制容斥，product trick。
T3，轉換貢獻形式，對顏色算貢獻。
T4，冒泡排序的刻畫。
浙公網安備 33010602011771號