Number Table
在 \(2\) 行 \(n\) 列的矩阵中，计算满足
- 矩阵内所有数组异或和为 \(0\)
- 每一行、每一列数字互异
- 每个数的取值范围为 \([0, 2^k)\)
的填数方案数
题意相当于每行内有 \(\dfrac{n (n - 1)}{2}\) 对不等关系的限制，每列内有 \(1\) 对不等关系的限制，总共 \(n^2\) 对不等关系限制的情况下，求出有多少种方案满足所有数的异或和为 \(0\)
假如不考虑不等关系的限制，答案很简单，就是前 \(2n - 1\) 个位置任选，最后一个位置凑成异或和为 \(0\) 即可
考虑不等限制时，建立一个图论模型，图上 \(2n\) 个点对应表中的 \(2n\) 个格子，并且有 \(n^2\) 条边对应 \(n^2\) 对不等关系
考虑用全集减去非法的方案， 非法的方案就是枚举一条边，强制边两边的点相等，但是这样又会多减，所以我们利用容斥原理，只要枚举边集的全部子集，然后强制这个子集内的边为相等，在此情况下计算方案数，并且乘上容斥系数之后再全加起来即可
这样对于一个枚举出来的子集，一张图被划分成若干个连通块，每个连通块上所有点上填的数都是相等的，如果一个连通块的大小是偶数，那么无论填多少都不会影响答案；当连通块大小为奇数时， 其等价于一个点。所以如果所有连通块的大小都是偶数，那么方案数就是 \(2^{k \times 连通块个数}\) ；如果不全是偶数，那方案数就是 \(2^{k \times (连通块个数 - 1)}\)
直接做复杂度过大，但是注意到其实我们计算的时候用的是连通块，答案也只和连通块个数以及是不是全是偶数大小有关，因此有更高效的做法：首先先统一用 \(2^{k \times 连通块个数}\) 来计算方案数，最后统一再除以 \(2^k\)，这样得到的是假设一定有奇数大小联通块情况的答案，暂时先不 考虑纯偶数大小连通块的情况。我们可以 DP，设 \(f_{a, b, c}\) 表示一个不完整的表格的方案数，其有 \(a\) 列是完整的；有 \(b\) 列仅上半部分保留，下半部分残缺；有 \(c\) 列仅下半部分保留，上半部分残缺，如图：
转移时枚举一个连通块，转移时除了连通块本身贡献的 \(2^k\) 种方案，还有连通块的容斥系数，这个容斥系数是所有能使得这个连通块处于连通状态的边集选法对应的容斥系数之和，即 \(\sum_{E' \subseteq E} (-1)^{|E'|} \times [E′确保此连通块能连通]\) ，此处的 \(E\) 是此连通块内部所有可能的边
枚举连通块转移时要注意顺序，一定要强制一个特殊点必须在连通块内，这样可以保证每一种拆分方法唯一，不然可能同一个划分方法被多种不同的顺序枚举，这个特殊点的选取方式并不唯一，比如可以强制如果 \(b\) 非 \(0\) ，就让右上 \(b\) 个点里面选第一个为特殊点，否则如果 \(c\) 非 \(0\)，就让左 下 \(c\) 个点里第一个作为特殊点，再否则就让中间 \(2a\) 个点的第一个当特殊点。
枚举连通块时，可以在图中右上的 \(b\) 个里面枚举了多少个算入连通块内；在左下的 \(c\) 个里面枚举了多少个算入连通块内；中间 \(2a\) 个点里面，有多少列是上下两点一起选的，有多少列是只选了上面，多少列只选了下面。这样总共需要枚举五维，之后再用计算一下有具体的选法数量，注意计算方案数时要考虑到上面强制枚举的一个特殊点
这样是一个 \(O(n^8)\) 复杂度的 DP，直接计算无法通过，但是上面各个维度之间有各种相互限制的关系导致常数非常小，仅为 \(\dfrac{1}{40320}\) ，故而能在时限内计算完成，计算出 \(f_{n, 0, 0}\) 后，再除以 \(2^k\) 就得到了假设有奇数大小连通块情况的答案，如果考虑纯偶数大小连通块的情况，其 实也可以如法炮制，再用类似的方法 DP 一遍即可，最后减去之前多算的一部分也就是本来是纯偶数大小连通块的情况，但是却按照 \(2^{ki \times (连通块个数 - 1)}\) 来计算的部分即可
接下来是连通块容斥系数的计算，设 \(g_{a, b, c}\) 表示一个连通块的容斥系数，且这个连通块的长相也如上图所示。连通这个限制比较难以处理，所以依然使用容斥的方法，用全集减去不连通图的系数，那么对任意图来说，因为每条边都可选可不选，最终容斥系数相抵消，容斥系数就是 \(0\) ；除非此图内没有任何边，此时容斥系数为 \(1\) 。不连通的情况的贡献是枚举一个连通块，剩余部分随意，只要不与这个连通块相连即可。枚举时依然是确定一个特殊点，然后枚举一个连通块要包含这个点，这样就强制枚举出了不连通图，且不重不漏。考虑如何计算剩余部分的贡献，还是如上结论， 如果剩余部分里面有边，那么贡献就是 \(0\) ，可以不用考虑，只有几种特殊情况无边，讨论一下即可。这 样可以在 \(O(n^3)\) 的时间内计算出 \(g\) 数组
另外，计算假设一定有奇数大小连通块的情况时，分析这个式子的含义，其实是等价于没有异或和为 \(0\) 的限制，只考虑不等的限制的情况的方案数再除以 \(2^k\) ，这样其实 只需要一个 \(O(n^3)\) 的 DP 即可。但是纯偶数大小连通块的部分依然要 \(O(n^8)\) 计算，这样整体复杂度是不变的，但是常数小了很多（因为纯偶数大小连通块的 DP 本身限制更多，常数更小，所以此优化效果还是非常好的）
#include <bits/stdc++.h>
using namespace std;
const int Mod = 998244353;
const int N = 4e1 + 7, SIZE = 2e2 + 7;
int f[N][N][N], h[N][N][N];
int g[N][N];
int fac[N << 3], inv[N << 3], invfac[N << 3];
int T, n, K;
inline int mi(int a, int b, int mod) {
int res = 1;
for (; b; b >>= 1, a = 1ll * a * a % mod)
if (b & 1)
res = 1ll * res * a % Mod;
return res;
}
inline void init() {
fac[0] = fac[1] = 1;
inv[0] = inv[1] = 1;
invfac[0] = invfac[1] = 1;
for (int i = 2; i < (N << 3); ++i) {
fac[i] = 1ll * fac[i - 1] * i % Mod;
inv[i] = 1ll * (Mod - Mod / i) * inv[Mod % i] % Mod;
invfac[i] = 1ll * invfac[i - 1] * inv[i] % Mod;
}
}
inline int dibnom(int n, int m) {
return m > n ? 0 : 1ll * fac[n] * invfac[n - m] % Mod * invfac[m] % Mod;
}
inline void clear() {
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
memset(h, 0, sizeof(h));
}
signed main() {
init();
scanf("%d", &T);
for (; T; --T) {
clear();
scanf("%d%d", &n, &K);
int w = mi(2, K, Mod);
f[0][0][1] = f[0][1][0] = 1;
for (int i = 2; i <= n; ++i)
f[0][0][i] = f[0][i][0] = Mod - 1ll * (i - 1) * f[0][i - 1][0] % Mod;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= n; ++j)
for (int k = 0; k <= n; ++k)
if (j > k)
f[i][j][k] = f[i][k][j];
else {
if (k)
f[i][j][k] = (f[i][j][k] + 1ll * f[i][j][k - 1] * k % Mod) % Mod;
f[i][j][k] = (f[i][j][k] + 1ll * f[i - 1][j + 1][k] * i % Mod) % Mod;
if (j)
f[i][j][k] = (f[i][j][k] + 1ll * f[i][j - 1][k] * j % Mod) % Mod;
f[i][j][k] = (f[i][j][k] + 1ll * (i - 1) * f[i - 1][j][k + 1] % Mod) % Mod;
if (j && k)
f[i][j][k] = (f[i][j][k] + 1ll * j * k % Mod * f[i][j - 1][k - 1] % Mod) % Mod;
f[i][j][k] = (f[i][j][k] + 1ll * (j * i + k * (i - 1)) * f[i - 1][j][k] % Mod) % Mod;
if (i > 1)
f[i][j][k] = (f[i][j][k] + 1ll * (i - 1) * (i - 1) * f[i - 2][j + 1][k + 1] % Mod) % Mod;
f[i][j][k] = (Mod - f[i][j][k]) % Mod;
}
g[0][0] = 1;
for (int i = 0; i < n; ++i)
for (int j = 0; j <= i; ++j) {
g[i + 1][j + 1] = (g[i + 1][j + 1] + 1ll * (w - i - j + Mod) % Mod * (w - i - j - 1 + Mod) % Mod * g[i][j] % Mod) % Mod;
g[i + 1][j] = (g[i + 1][j] + 1ll * (w - i - j + Mod) % Mod * j * 2 % Mod * g[i][j] % Mod) % Mod;
if (j)
g[i + 1][j - 1] = (g[i + 1][j - 1] + 1ll * j * j * g[i][j] % Mod) % Mod;
}
h[0][0][0] = 1;
for (int c = 0; c <= n; ++c)
for (int a = 0; a + c <= n; ++a)
for (int b = 0; a + b + c <= n; ++b)
if (!((a + b) & 1) && (c || a || b)) {
for (int C = 0; C <= c; ++C)
for (int A = 0; A <= a; ++A)
for (int B = 0; B <= b; ++B)
for (int k1 = 0; C + k1 <= c; ++k1)
for (int k2 = 0; C + k1 + k2 <= c; ++k2)
if (!((A + B + k1 + k2) & 1))
if (c) {
if (C + k1)
h[c][a][b] = (h[c][a][b] + 1ll * dibnom(c - 1, C + k1 - 1) * dibnom(c - C - k1, k2) % Mod * dibnom(C + k1, C) % Mod * dibnom(a, A) % Mod * dibnom(b, B) % Mod * h[c - C - k1 - k2][a - A + k2][b - B + k1] % Mod * w % Mod * f[C][A + k1][B + k2] % Mod) % Mod;
} else if (a) {
if (A)
h[c][a][b] = (h[c][a][b] + 1ll * dibnom(a - 1, A - 1) * dibnom(b, B) % Mod * h[c - C][a - A][b - B] % Mod * w % Mod * f[C][A][B] % Mod) % Mod;
} else if (b) {
if (B)
h[c][a][b] = (h[c][a][b] + 1ll * dibnom(b - 1, B - 1) * h[c - C][a - A][b - B] % Mod * w % Mod * f[C][A][B] % Mod) % Mod;
}
}
int G = 0;
for (int i = 0; i <= n; ++i)
G = (G + g[n][i]) % Mod;
printf("%d\n", (1ll * (G - h[n][0][0] + Mod) % Mod * mi(w, Mod - 2, Mod) % Mod + h[n][0][0]) % Mod);
}
return 0;
}
Simple Tree Problem
给定一棵树，第 \(i\) 个点有点权 \(a_i\) ，第 \(i\) 条边有边权 \(k_i\) 。定义
- \(f(x, T)\) 为树 \(T\) 中点权等于 \(x\) 的点的数量
- \(g(y, T)\) 为满足 \(f(x, T)\) 不小于 \(y\) 的最大的 \(x\) ，如果这样的 \(x\) 不存在，则 \(g(y, T) = 0\)
对于第 \(i\) 条边，若删除，则会将原树分为两棵新树 \(T_{i_1}, T_{i_2}\) ，对于第 \(i\) 条边，计算
\[\max \{ g(k_i, T_{i_1}), g(k_i, T_{i_2}) \} \]（每次并不会真正删去这条边）
对于每条边的询问，相当于询问只有该子树内的信息的最大值以及全局的信息只扣掉该子树内信息的最大值，对于这两种情况都可以使用线段树合并去处理答案。特别的，处理第二种情况时，子树内维护的是被删除过的值的最大剩余数量，而对于未被删除过的值，可以首先预处理出一棵存有完整信息的权值线段树，在合并过程中残树和整树一起递归，用两棵树的信息一起合并上传，就可以得到当前子树外的真实最大值，能同时递归的原因是残树是整树的子图
时间复杂度 \(O(n \log n)\)
#include <bits/stdc++.h>
class IO {
#define MAXSIZE (1 << 17)
public:
inline IO(FILE *_stream = stdin, FILE *__stream = stdout) {
sta_int[0] = '\0',
s1 = s3 = ibuf, s2 = obuf,
in_stream = _stream, out_stream = __stream;
}
inline ~IO() {
fwrite(obuf, 1, s2 - obuf, out_stream), s2 = obuf;
fclose(in_stream), fclose(out_stream);
}
inline int get() {
return (s1 == s3 && (s3 = (s1 = ibuf) + fread(ibuf, 1, MAXSIZE, in_stream), (s1 == s3))) ? 0 : *s1++;
}
inline void put(char c) {
(s2 - obuf == MAXSIZE) && (fwrite(obuf, 1, s2 - obuf, out_stream), s2 = obuf), *s2++ = c;
}
inline IO &getline(char *s) {
register char c = get();
for (; isspace(c); c = get());
for (; c != '\n' && c; *s++ = c, c = get());
return *s = '\0', *this;
}
inline IO &getline(std::string &s) {
register char c = get();
for (; isspace(c); c = get());
for (s = c, c = get(); c != '\n' && c; s.push_back(c), c = get());
return *this;
}
template<class T>
inline IO &read(T &x) {
register int c = get();
while (isspace(c) && c)
c = get();
register bool f = (c == '-');
x = 0, isdigit(c) || (c = get());
while (isdigit(c))
x = (x << 1) + (x << 3) + (c & 15), c = get();
return f && (x = ~x + 1), *this;
}
inline IO &read(char &c) {
for (c = get(); isspace(c); c = get());
return *this;
}
inline IO &read(char *s) {
register char c = get();
for (; isspace(c) && c; c = get());
for (; !isspace(c) && c; *s++ = c, c = get());
return *s = '\0', *this;
}
inline IO &read(std::string &s) {
register char c = get();
for (; isspace(c); c = get());
for (s = c, c = get(); !isspace(c) && c; s.push_back(c), c = get());
return *this;
}
template<class T>
inline IO &write(T x) {
register char *p = sta_int;
for ((x < 0) && (put('-'), x = ~x + 1), *++p = (x % 10) | '0', x /= 10; x; *++p = (x % 10) | '0', x /= 10);
for (; *p; put(*p--));
return *this;
}
inline IO &write(const char c) {
return put(c), *this;
}
inline IO &write(char *s) {
for (; *s; put(*s++));
return *this;
}
inline IO &write(const char *s) {
for (; *s; put(*s++));
return *this;
}
inline IO &write(std::string str) {
return write(str.c_str());
}
template<class T, class ...Args>
inline IO &read(T &x, Args &...args) {
return read(x), read(args...);
}
template<class T, class ...Args>
inline IO &write(T x, Args ...args) {
return write(x), write(args...);
}
template<class T>
inline IO &operator >> (T &x) {
return read(x);
}
template<class T>
inline IO &operator << (const T x) {
return write(x);
}
protected:
char ibuf[MAXSIZE], obuf[MAXSIZE], *s1, *s2, *s3, sta_int[27];
FILE *in_stream, *out_stream;
#undef MAXSIZE
} io;
using namespace std;
const int N = 1e6 + 7;
struct Edge {
int v, idx;
};
vector<Edge> e[N];
vector<int> vec;
int a[N], ans[N], lim[N], cnt[N];
int T, n;
namespace SMT {
const int SIZE = 3e7 + 7;
int s[SIZE], lc[SIZE], rc[SIZE];
int rt[N];
int tot, root;
inline void clear() {
for (int i = 1; i <= tot; ++i)
s[i] = lc[i] = rc[i] = 0;
fill(rt + 1, rt + n + 1, 0);
root = tot = 0;
}
void insert(int p, int &x, int node, bool rev, int l, int r) {
if (!x)
x = ++tot;
if (l == r) {
s[x] = (rev ? cnt[l] - 1 : 1);
return;
}
int mid = (l + r) >> 1;
if (p <= mid)
insert(p, lc[x], lc[node], rev, l, mid);
else
insert(p, rc[x], rc[node], rev, mid + 1, r);
s[x] = max(s[lc[x] ? lc[x] : lc[node]], s[rc[x] ? rc[x] : rc[node]]);
}
void merge(int &X, int Y, int x, bool rev, int l, int r) {
if (!X || !Y) {
X |= Y;
return;
}
if (l == r) {
s[X] += s[Y] - (rev ? cnt[l] : 0);
return;
}
int mid = (l + r) >> 1;
merge(lc[X], lc[Y], lc[x], rev, l, mid);
merge(rc[X], rc[Y], rc[x], rev, mid + 1, r);
s[X] = max(s[lc[X] ? lc[X] : lc[x]], s[rc[X] ? rc[X] : rc[x]]);
}
int query(int val, int x, int node, int l, int r) {
if (s[x ? x : node] < val)
return 0;
if (l == r)
return vec[l - 1];
int mid = (l + r) >> 1, res = query(val, rc[x], rc[node], mid + 1, r);
if (!res)
res = query(val, lc[x], lc[node], l, mid);
return res;
}
void build(int &x, int l, int r) {
if (!x)
x = ++tot;
if (l == r) {
s[x] = cnt[l];
return;
}
int mid = (l + r) >> 1;
build(lc[x], l, mid), build(rc[x], mid + 1, r);
s[x] = max(s[lc[x]], s[rc[x]]);
}
} // namespace SMT
inline void AddEdge(int u, int v, int idx) {
e[u].push_back((Edge) {v, idx});
}
void dfs(int u, int fa, bool rev) {
SMT::insert(a[u], SMT::rt[u], SMT::root, rev, 1, vec.size());
for (Edge it : e[u]) {
int v = it.v, idx = it.idx;
if (v == fa)
continue;
dfs(v, u, rev);
ans[idx] = max(ans[idx], SMT::query(lim[idx], SMT::rt[v], SMT::root, 1, vec.size()));
SMT::merge(SMT::rt[u], SMT::rt[v], SMT::root, rev, 1, vec.size());
}
}
inline void clear() {
for (int i = 1; i <= n; ++i)
e[i].clear();
fill(cnt + 1, cnt + vec.size() + 1, 0);
fill(ans + 1, ans + n, 0);
vec.clear();
}
int main() {
io.read(T);
for (; T; --T) {
io.read(n);
for (int i = 1; i <= n; ++i) {
io.read(a[i]);
vec.push_back(a[i]);
}
for (int i = 1, u, v; i < n; ++i) {
io.read(u, v, lim[i]);
AddEdge(u, v, i), AddEdge(v, u, i);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (int i = 1; i <= n; ++i) {
a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
++cnt[a[i]];
}
dfs(1, 0, false), SMT::clear();
SMT::build(SMT::root, 1, vec.size());
dfs(1, 0, true), SMT::clear();
for (int i = 1; i < n; ++i)
io.write(ans[i], '\n');
clear();
}
return 0;
}
Simple Set Problem
给定 \(n\) 个集合，从每个集合中选出一个数组成一个可重集，求新可重集的极差最小值
将所有集合中的元素排序，尺取法解决即可
时间复杂度 \(O(n \log n)\)
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;
const int N = 1e6 + 7;
vector<pair<int, int> > vec;
int buc[N];
int T, n;
signed main() {
scanf("%d", &T);
for (; T; --T) {
vec.clear();
memset(buc, 0, sizeof(buc));
scanf("%d", &n);
for (int i = 1, c; i <= n; ++i) {
scanf("%d", &c);
for (int j = 1, x; j <= c; ++j) {
scanf("%d", &x);
vec.push_back(make_pair(x, i));
}
}
sort(vec.begin(), vec.end());
int ans = inf, cnt = 0;
for (int i = 0, j = 0; i < vec.size(); ++i) {
cnt += !buc[vec[i].second], ++buc[vec[i].second];
while (j < i && buc[vec[j].second] > 1)
--buc[vec[j].second], ++j;
if (cnt == n)
ans = min(ans, vec[i].first - vec[j].first);
}
printf("%d\n", ans);
}
return 0;
}
Data Generation
求 \(ans\) 的期望
记随机变量 \(X_i = [a_i = i]\) ，则答案为 \(n - E(\sum_{i = 1}^n X_i)\) 。由期望的线性性，得 \(E(\sum_{i = 1}^n X_i) = \sum_{i = 1}^n E(X_i) = n E(X_1) = n \times P(a_0 = 0)\)
考虑设 \(f_k\) 表示随机 \(k\) 次 \(P(a_0 = 0)\) 的值，需要求 \(f_m\) ，有 \(f_k = \dfrac{1 + (n - 1)^2}{n^2} f_{k - 1} + \dfrac{2}{n^2} (1 - f_{k - 1}) = \dfrac{n - 2}{n} f_{k - 1} + \dfrac{2}{n^2}\)
可配凑为等比数列求解
时间复杂度 \(O(\log \max(n, m))\)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll Mod = 998244353;
inline ll mi(ll a, ll b, ll mod) {
a %= mod;
ll res = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1)
res = res * a % mod;
return res;
}
inline ll inv(ll x) {
return mi(x, Mod - 2, Mod);
}
signed main() {
int T;
scanf("%d", &T);
for (ll n, m; T; --T) {
scanf("%lld%lld", &n, &m);
ll a = (Mod + 1 - inv(n) * 2 % Mod) % Mod;
ll t = inv(n);
ll f = (mi(a, m, Mod) * (Mod + 1 - t) % Mod + t) % Mod;
printf("%lld\n", n % Mod * (Mod + 1 - f) % Mod);
}
return 0;
}
Teyvat
给定一张无向联通图， \(q\) 次查询，每次给定一个集合 \(\{ a_1, a_2, \cdots, a_k \}\) ，询问有多少点对 \((S, T)\) 使得 \(S\) 到 \(T\) 的任何简单路径正好经过集合内的所有点一次
考虑对图建出广义圆方树，每次询问一个点集，点集中的点用圆方树上的圆点表示出来
如果点集中的所有点可以作为一点路径 \((a, b)\) 的原图中必经点，那么 \((a, b)\) 在圆方树上可以覆盖点集中的所有点对应点，分类讨论：
- \(k = 1\) ：预处理统计圆方树上通过有多少圆点点对路径覆盖过这一个点
- \(k > 1\) 且这 \(k\) 个点在圆方树上不能被一条路径覆盖：答案为 \(0\)
- \(k > 1\) 且这 \(k\) 个点在圆方树上能被一条路径覆盖：取出最远点 \((u, v)\) ，若 \(u, v\) 不为祖孙关系，则答案为 \(siz_u \times size_v\) （其中 \(siz_u\) 表示 \(u\) 子树内的圆点数量）；若 \(u, v\) 为祖孙关系，不妨令 \(u\) 为祖先，则答案为 \((n - siz_w) \times size_v\) ，其中 \(w\) 为 \(u\) 的儿子，\(v\) 的祖先
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 5e5 + 7;
vector<int> e[N];
stack<int> sta;
int dfn[N], low[N];
int T, n, m, q, dfstime;
namespace Tree {
const int SIZE = 1e6 + 7;
vector<int> e[SIZE];
ll dp[SIZE];
int fa[SIZE], dep[SIZE], siz[SIZE], son[SIZE], top[SIZE], siz0[SIZE];
int dfn[SIZE], low[SIZE];
int tot, dfstime;
inline void AddEdge(int u, int v) {
e[u].push_back(v);
}
void dfs1(int u, int f) {
siz0[u] = u <= n, dp[u] = 0;
for (int v : e[u])
if (v != f) {
dfs1(v, u);
siz0[u] += siz0[v];
dp[u] += 1ll * siz0[v] * (siz0[v] - 1) >> 1;
}
dp[u] += 1ll * (n - siz0[u]) * (n - siz0[u] - 1) >> 1;
}
void dfs2(int u, int f) {
fa[u] = f, siz[u] = 1, dep[u] = dep[f] + 1, son[u] = 0;
int Max = 0;
for (int v : e[u])
if (v != f) {
dfs2(v, u);
siz[u] += siz[v];
if (siz[v] > Max)
Max = siz[v], son[u] = v;
}
}
void dfs3(int u, int topf) {
top[u] = topf, dfn[u] = ++dfstime;
if (son[u])
dfs3(son[u], topf);
for (int v : e[u])
if (v != fa[u] && v != son[u])
dfs3(v, v);
low[u] = dfstime;
}
inline int LCA(int u, int v) {
if (dep[top[u]] > dep[top[v]])
swap(u, v);
return top[u] == top[v] ? (dep[u] > dep[v] ? v : u) : LCA(u, fa[top[v]]);
}
inline int dis(int u, int v) {
return dep[u] + dep[v] - (dep[LCA(u, v)] << 1);
}
inline int find(int v, int tp) {
for (; top[v] != top[tp]; v = fa[top[v]])
if (fa[top[v]] == tp)
return top[v];
return son[tp];
}
inline bool cmp(const int &x, const int &y) {
return dfn[x] < dfn[y];
}
inline ll query(int k, vector<int> vec) {
if (k == 1)
return (1ll * n * (n - 1) >> 1) - dp[vec.front()] + 1;
sort(vec.begin(), vec.end(), cmp);
int u = vec.back();
vec.pop_back();
int v = vec.back();
vec.pop_back();
if (dep[u] > dep[v])
swap(u, v);
int d = dis(u, v);
for (int it : vec)
if (dis(u, it) + dis(it, v) != d)
if (dfn[v] <= dfn[it] && low[it] <= low[v])
v = it, d = dis(u, v);
else if (dfn[u] <= dfn[it] && low[it] <= low[u])
u = it, d = dis(u, v);
else if (dfn[u] <= dfn[v] && low[v] <= low[u])
u = it, d = dis(u, v);
else
return 0;
if (dfn[u] > dfn[v])
swap(u, v);
if (dfn[u] <= dfn[v] && low[v] <= low[u])
return 1ll * (n - siz0[find(v, u)]) * siz0[v];
else
return 1ll * siz0[u] * siz0[v];
}
inline void clear(int n) {
for (int i = 1; i <= tot; ++i)
e[i].clear();
tot = n, dfstime = 0;
}
} // namespace Tree
inline void AddEdge(int u, int v) {
e[u].push_back(v);
}
void Tarjan(int u, int fa) {
dfn[u] = low[u] = ++dfstime;
sta.push(u);
for (int v : e[u]) {
if (v == fa)
continue;
if (!dfn[v]) {
Tarjan(v, u);
if (low[v] >= dfn[u]) {
int k = 0;
++Tree::tot;
Tree::AddEdge(u, Tree::tot), Tree::AddEdge(Tree::tot, u);
do {
k = sta.top(), sta.pop();
Tree::AddEdge(Tree::tot, k), Tree::AddEdge(k, Tree::tot);
} while (k != v);
} else
low[u] = min(low[u], low[v]);
} else
low[u] = min(low[u], dfn[v]);
}
}
inline void clear(int n) {
for (int i = 1; i <= n; ++i)
e[i].clear();
fill(dfn + 1, dfn + n + 1, 0);
dfstime = 0;
}
signed main() {
io.read(T);
for (; T; --T) {
io.read(n, m, q);
Tree::clear(n), clear(n);
for (int i = 1, u, v; i <= m; ++i) {
io.read(u, v);
AddEdge(u, v), AddEdge(v, u);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i])
Tarjan(i, 0);
Tree::dfs1(1, 0), Tree::dfs2(1, 0), Tree::dfs3(1, 1);
for (int i = 1; i <= q; ++i) {
int k;
vector<int> S;
io.read(k);
for (int i = 1, x; i <= k; ++i) {
io.read(x);
S.push_back(x);
}
io.write(Tree::query(k, S), '\n');
}
}
return 0;
}
PSO
\[E(X) = \dfrac{(n - 1) \times 1 + \dfrac{(n - 2) \times (n - 1)}{2} \times 2}{\dfrac{(n - 1) \times n}{2}} = 2 - \dfrac{2}{n} \\ X_{\max} = \begin{cases} 1 & n = 2 \\ 2 & n > 2 \end{cases} \]给定一张 \(n\) 个点的菊花图，所有边长度都是 \(1\)，求选两个点的期望距离和最大距离
时间复杂度 \(O(1)\)
#include <bits/stdc++.h>
using namespace std;
signed main() {
int T;
scanf("%d", &T);
for (double n; T; --T) {
scanf("%lf", &n);
printf("%.9lf %.9lf\n", 2.0 - 2.0 / n, n == 2 ? 1.0 : 2.0);
}
return 0;
}
Guess
记 \(S(n) = \sum_{d | n} \mu(\dfrac{n}{d}) \ln d\) ，求 \(e^{S(n)} \bmod 998244353\)
由于 \(d\) 与 \(\dfrac{n}{d}\) 对称，不妨将 \(S(n)\) 记作 \(\sum_{d | n} \mu(d) \ln(\dfrac{n}{d})\)
若 \(n = 1\) ，则 \(S(n) = S(1) = 1\)
否则记 \(n\) 的唯一分解为 \(n = \prod_{i = 1}^k p_i^{q_i}\) ，此时 \(k \geq 1\) 。由于 \(\mu(d) \not = 0\) 当且仅当 \(d\) 不含平方因子，这些 \(d\) 形如 \(d = \prod_{i = 1}^k p_i^{c_i}\) ，其中 \(c_i \in \{ 0, 1 \}\) ，此时枚举 \(d\) 就等价于枚举 \(R = \{ 1, 2, \cdots, k \}\) 的子集，则 \(S(n) = \sum_{T \subseteq R} (-1)^{|T|} (\ln n - \sum_{i \in T} \ln p_i)\) ，拆成两部分
其中 \(\ln n \sum_{T \subseteq R} (-1)^{|T|} = \ln n \sum_{i = 0}^k \dbinom{k}{i} (-1)^i = \ln n [k = 1]\)
另一边
\[\begin{aligned} & -\sum_{T \subseteq R} (-1)^{|T|} \sum_{i \in T} \ln p_i \\ =& -\sum_{i = 1}^k \ln p_i \sum_{i \in T \subseteq R} (-1)^{|T|} \\ =& \sum_{i = 1}^k \ln p_i \sum_{j = 0}^{k - 1} \dbinom{k - 1}{j} (-1)^j \end{aligned} \]若 \(k = 1\) 时，上式为 \(\ln p\) ，否则为 \(0\)
综上所述，当 \(n\) 为某个素数 \(p\) 的正整数次幂时， \(S(n) = \ln p, e^{S(n)} = p\) ，否则 \(S(n) = 0, e^{S(n)} = 1\)
用 Pollard-Rho算法质因数分解即可
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll Mod = 998244353;
set<ll> factor;
inline ll mi(ll a, ll b, ll p) {
ll res = 1;
for (; b; b >>= 1, a = (__int128) a * a % p)
if (b & 1)
res = (__int128) res * a % p;
return res;
}
inline ll mul(ll x, ll y, ll p) {
ll z = (long double) x / p * y;
ll res = (ull) x * y - (ull) z * p;
return (res + p) % p;
}
inline ll gcd(ll a, ll b) {
if (!a || !b)
return a | b;
while (a ^= b ^= a ^= b %= a);
return b;
}
inline bool MillerRabin(ll k, ll p, ll d, ll r) {
ll a = rand() % (p - 2) + 2, x = mi(a, d, p);
if (x == 1 || x == p - 1)
return true;
for (ll i = 0; i < r - 1; ++i) {
x = mul(x, x, p);
if (x == p - 1)
return true;
}
return false;
}
inline bool IsPrime(ll p) {
if (p == 1)
return false;
if (p == 2 || p == 3)
return true;
ll d = p - 1, r = 0;
while (!(d & 1))
++r, d >>= 1;
vector<ll> k_prime = (vector<ll>) {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for (ll k : k_prime)
if (!MillerRabin(k, p, d, r))
return false;
return true;
}
inline ll PollardRho(ll n) {
ll s = 0, t = 0, c = rand() % (n - 1) + 1;
for (ll goal = 1, val = 1;; goal <<= 1, s = t, val = 1) {
for (ll step = 1; step <= goal; ++step) {
t = (mul(t, t, n) + c) % n;
val = mul(val, abs(t - s), n);
if (!(step % 127)) {
ll d = gcd(val, n);
if (d > 1)
return d;
}
}
ll d = gcd(val, n);
if (d > 1)
return d;
}
}
void breakdown(ll x) {
if (x < 2)
return;
if (IsPrime(x)) {
factor.insert(x);
return;
}
ll p = x;
while (p >= x)
p = PollardRho(x);
while (!(x % p))
x /= p;
breakdown(x), breakdown(p);
}
signed main() {
srand(time(NULL));
int T;
scanf("%d", &T);
for (ll n; T; --T) {
scanf("%lld", &n);
factor.clear();
breakdown(n);
printf("%lld ", factor.size() == 1 ? (*factor.begin()) % Mod : 1);
}
return 0;
}
String and GCD
给定字符串 \(S[1 : n]\) ，求 \(f(i) = \sum_{j = 1}^{i - 1} [S[1 : j] = S[i - j + 1 : i]] \times \gcd(i, j)\)
对于 \(S[1 : j] = S[i - j + 1 : i]\) 的限制，显然可以跑 KMP 构建 fail 树，若等式成立，则必有 fail 树上 \(j\) 是 \(i\) 的祖先
对于 \(\gcd(i, j)\) ，通过莫比乌斯反演得到 \(\gcd(i, j) = \sum_{d | i, d | j} \varphi(d)\)
对于所有的 \(i\) ，预处理所有因子 \(d\) ，在深搜 fail 树时记录一个桶 \(cnt_d\) 表示 \(i\) 的所有祖先 \(j\) 满足 \(d | j\) 的个数， \(f(i) = \sum_{d | i} cnt_d \times \varphi(d)\)
时间复杂度 \(O(n \log n)\)
#include <bits/stdc++.h>
using namespace std;
const int Mod = 998244353;
const int N = 1e6 + 7;
vector<int> d[N], e[N];
int prime[N], phi[N];
int fail[N], cnt[N];
char s[N];
bool IsPrime[N];
int n, tot;
inline void init() {
for (int i = 1; i < N; ++i)
for (int j = i; j < N; j += i)
d[j].push_back(i);
memset(IsPrime, true, sizeof(IsPrime));
tot = 0;
IsPrime[1] = false, phi[1] = 1;
for (int i = 2; i < N; ++i) {
if (IsPrime[i])
prime[++tot] = i, phi[i] = i - 1;
for (int j = 1; j <= tot && i * prime[j] < N; ++j) {
IsPrime[i * prime[j]] = false;
if (i % prime[j])
phi[i * prime[j]] = phi[prime[j]] * phi[i];
else {
phi[i * prime[j]] = prime[j] * phi[i];
break;
}
}
}
}
inline void clear() {
for (int i = 0; i < N; ++i)
e[i].clear();
}
inline void AddEdge(int u, int v) {
e[u].push_back(v);
}
int dfs(int u) {
int res = 1;
for (int v : d[u]) {
res = (res + 1ll * cnt[v] * phi[v] % Mod) % Mod;
++cnt[v];
}
for (int v : e[u])
res = 1ll * res * dfs(v) % Mod;
for (int v : d[u])
--cnt[v];
return res;
}
signed main() {
int size(512 << 20);
__asm__("movq %0, %%rsp\n" ::"r"((char *)malloc(size) + size)); // 手动开大栈空间
init();
int T;
scanf("%d", &T);
for (; T; --T) {
clear();
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 2, j = 0; i <= n; ++i) {
while (j && s[i] != s[j + 1])
j = fail[j];
if (s[i] == s[j + 1])
++j;
fail[i] = j;
}
for (int i = 1; i <= n; ++i)
AddEdge(fail[i], i);
printf("%d\n", dfs(0));
}
exit(0);
}
WO MEI K
给定一棵树，设 \(f_{u, v}\) 表示 \(u, v\) 间简单路径上边权只出现一次的边的数量，对于所有 \(k \in [1, n]\) ，求随机选 \(k\) 个点时 \(\sum_{i = 1}^k \sum_{j = i + 1}^k f_{i, j} \bmod 998244353\) 的期望，输出 \(k\) 从 \(1 \sim n\) 的答案的异或和
该式子的期望等于求出 \(\dfrac{该式子的总和}{\dbinom{n}{k}}\)
先考虑 \(k = 2\) ，相当于所有两个不同的点之间只出现过一条边的个数的个数的和，这是一个经典问题，考虑每条边的贡献，答案就是所有边的贡献和。对于每条边，其贡献就是有多少个点对 \((x, y)\) 满足其简单路径经过这条边且该边权值只出现一次。设 \(1\) 为根，对于一条边 \((u, v, w)\) 假设 \(x\) 在 \(u\) 的子树中，那么 \(y\) 就不能在 \(u\) 的子树中。\(x\) 可以放的地方就是所有 \(x\) 到 \(u\) 之间没有边权为 \(w\) 的边的位置， \(y\) 同理。对于 \(x\) 的位置的数量，可以直接在树上从下往上求出；对于 \(y\) 的放置位置有两种情况
- \(v\) 到根节点有边权为 \(w\) 的边：直接存权值为 \(w\) 的最近父节点即可
- \(v\) 到根节点没有边权为 \(w\) 的边：减去其他子树从根往下的第一个权值为 \(w\) 的边的子树即可
对于 \(k > 2\) 的情况，由于对 \(k = 2\) 我们求的是两个点对某条边的贡献，其他的 \(k - 2\) 个点可以任意选，所以只要将 \(k = 2\) 的答案乘上 \(\dbinom{n - 2}{k - 2}\) 即可
时间复杂度 \(O(n)\)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int Mod = 998244353;
const int N = 2e5 + 7;
vector<pair<int, int> > e[N];
vector<int> stk[N];
int siz[N], dp[N << 1], up[N];
int inv[N];
int T, n;
inline void init() {
inv[0] = inv[1] = 1;
for (int i = 2; i < N; ++i)
inv[i] = 1ll * (Mod - Mod / i) * inv[Mod % i] % Mod;
}
inline void clear() {
for (int i = 0; i < N; ++i)
e[i].clear(), stk[i].clear();
}
inline void AddEdge(int u, int v, int w) {
e[u].push_back(make_pair(v, w));
}
void dfs(int u, int f) {
for (pair<int, int> it : e[u]) {
int v = it.first, w = it.second;
if (v == f)
continue;
stk[w].push_back(v);
dfs(v, u);
stk[w].pop_back();
siz[u] += siz[v];
up[v] = stk[w].size() ? stk[w].back() : n + w;
dp[up[v]] -= siz[v];
}
dp[u] += siz[u];
}
signed main() {
init();
scanf("%d", &T);
for (; T; --T) {
clear();
scanf("%d", &n);
for (int i = 0, u, v, w; i < n - 1; ++i) {
scanf("%d%d%d", &u, &v, &w);
--u, --v, --w;
AddEdge(u, v, w), AddEdge(v, u, w);
}
for (int i = 0; i < n; ++i)
siz[i] = 1, dp[i] = 0;
for (int i = n; i < n * 2; ++i)
dp[i] = n;
dfs(0, -1);
int res = 0;
for (int i = 1; i < n; ++i)
res = (res + 1ll * dp[i] * dp[up[i]] % Mod) % Mod;
int ans = 0;
for (int i = 1; i <= n; ++i)
ans ^= 1ll * res * i % Mod * (i - 1) % Mod * inv[n] % Mod * inv[n - 1] % Mod;
printf("%d\n", ans);
}
return 0;
}
Kong Ming Qi
给定一张 \((n + 2) \times (m + 2)\) 的棋盘，其中中间的 \(n \times m\) 个格子有棋，走棋规则如下
求最终棋盘上剩下的最小棋子数量
不妨设 \(n \leq m\) ，分类讨论
- 当 \(n = 1\) 时，答案显然为 \(\lceil \dfrac{m}{2} \rceil\)
- 否则当 \(m \geq 5\) 时， \(n \times m\) 的情况下的答案等价于 \(n \times (m - 3)\) 情况下的答案，证明附后
- 因此我们将所有情况都转化为 \(2 \leq n\ leq m \leq 4\) 的情况，手算即可
时间复杂度 \(O(1)\)
情况二的证明：
先定义一个基本操作
由此操作我们可以一次消掉 \(1 \times 3\) 区域的棋子（注意前提条件），那么当 \(n \geq 3\) 时利用此操作可以将问题转化为 \(n \times (m - 3)\) 的情况
用此方法可以将 \(2 \times m\) 转化为 \(2 \times (m - 3)\)
#include <bits/stdc++.h>
using namespace std;
const int ans[5][5] = {
{1, 1, 2, 2, 3},
{1, 1, 2, 1, 1},
{2, 2, 2, 2, 2},
{2, 1, 2, 1, 1},
{3, 1, 2, 1, 1}
};
signed main() {
int T;
scanf("%d", &T);
for (int n, m; T; --T) {
scanf("%d%d", &n, &m);
if (n > m)
swap(n, m);
if (n == 1) {
printf("%d\n", (m + 1) / 2);
continue;
}
if (n > 5)
n = n % 3 + 3;
if (m > 5)
m = m % 3 + 3;
printf("%d\n", ans[n - 1][m - 1]);
}
return 0;
}
Circuit
求有向图的最小环长度与数量
考虑不重不漏地统计每个合法的环，对于一个环，只有枚举到标号最大的点的时候 我们才把方案计入答案
考虑 Floyd 算法如何实现，在维护 \(dis_{i, j}\) 表示 \(i\) 到 \(j\) 的最短距离，\(cnt_{i, j}\)表示 \(i\) 到 \(j\) 的最短路数量
Floyd 有三层循环实现，当最外层循环枚举到 \(k\) 时，\(dis_{i, j}\) 表示除了 \(i, j\) ，其余点 \(\leq k\) 的最短距离，枚举一条边 \((k, i)\) ，将此时的 \(dis_{i, k}\) 拼接上，由 \(w(k, i) + dis_{i, k}\) 更新最小环即可
时间复杂度 \(O(n^3)\)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll inf = 1e18;
const int Mod = 998244353;
const int N = 5e2 + 7;
ll dis[N][N];
int a[N][N], cnt[N][N];
int T, n, m;
inline void clear() {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
a[i][j] = 0, dis[i][j] = inf;
for (int i = 0; i < N; ++i)
dis[i][i] = 0;
}
signed main() {
scanf("%d", &T);
for (; T; --T) {
clear();
scanf("%d%d", &n, &m);
for (int i = 1, u, v, w; i <= m; ++i) {
scanf("%d%d%d", &u, &v, &w);
a[u][v] = dis[u][v] = w, cnt[u][v] = 1;
}
ll ans1 = inf;
int ans2 = 0;
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (dis[i][j] > dis[i][k] + dis[k][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
cnt[i][j] = 1ll * cnt[i][k] * cnt[k][j] % Mod;
} else if (dis[i][j] == dis[i][k] + dis[k][j])
cnt[i][j] = (cnt[i][j] + 1ll * cnt[i][k] * cnt[k][j] % Mod) % Mod;
for (int i = 1; i < k; ++i)
if (a[k][i])
if (a[k][i] + dis[i][k] < ans1)
ans1 = a[k][i] + dis[i][k], ans2 = cnt[i][k];
else if (a[k][i] + dis[i][k] == ans1)
ans2 = (ans2 + cnt[i][k]) % Mod;
}
if (ans1 == inf)
puts("-1 -1");
else
printf("%lld %d\n", ans1, ans2);
}
return 0;
}
a-b Problem
Alice 和 Bob 在玩一个小游戏。有 \(n\) 块石头。Alice 和 Bob 轮流选石头，Alice先选。每个人一次只能挑选一块石头，直到所有的石头都消失。每块石头都有两个属性 \(a_i, b_i\) 。当 Alice 选一块石头时，她会获得 \(a_i\) 积分；当 Bob 挑选一块石头时，他会获得 \(b_i\) 积分。每个人的总分是他们在挑选石头时获得的积分之和。两个玩家都希望最大化他们分数之间的差异，目标是让自己的分数减去对手的分数尽可能大。求 Alice 的分数减去 Bob 的分数的最终结果
考虑转化一下问题，假如一开始所有石子全在 Bob 手里，那么题中轮到 Alice 取时就拿走一个 Bob 手中的石子，轮到 Bob 取时 Bob 就藏起来一个石子不让 Alice 拿，这样显然与之前的问题等价。 然后 Alice 取时自己获得 \(a_i\) 的分数，Bob 失去 \(b_i\) 的分数，相当于拉开了 \(a_i + b_i\) 点分数差，所以 Alice 一定会优先取 \(a_i + b_i\) 最大的石子，而 Bob 也会优先藏住 \(a_i + b_i\) 最大的石子，所以只需要按
\(a_i + b_i\) 排序再轮流按顺序取即可
时间复杂度 \(O(n \log n)\)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 7;
pair<ll, ll > a[N];
inline bool cmp(const pair<ll, ll> &lhs, const pair<ll, ll> &rhs) {
return lhs.first + lhs.second > rhs.first + rhs.second;
}
signed main() {
int T;
scanf("%d", &T);
for (int n; T; --T) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%lld%lld", &a[i].first, &a[i].second);
sort(a + 1, a + 1 + n, cmp);
ll ansa = 0, ansb = 0;
for (int i = 1; i <= n; ++i)
if (i & 1)
ansa += a[i].first;
else
ansb += a[i].second;
printf("%lld\n", ansa - ansb);
}
return 0;
}