这段时间比赛的一些题 和 nKessi、duanyu 讲的题目。太偏计数、数学的基本上没办法做了。
A. 出关
http://222.180.160.110:61235/contest/6462/problem/1
给定 \(s\)，对于一个空串，任意利用下列三种操作，使其变为 \(s\)，求最小代价：
- 在末尾添加字符 \(c\)，代价为 \(t_{0,c}\)；
- 复制整个字符串并粘贴在末尾，代价为 \(t_1\)；
- 删除末尾字符，代价为 \(t_2\)。
\(|s|\le 10^6\)。
可以预处理出对于每个 \(i\) 结尾，最多可以复制到哪个地方，发现要求 \(z_i=lcp(s_{1\dots n},s_{i+1\dots n})\)。那么一个 \(i\) 的最远转移点 \(r_i=i+z_{i+1}\)，用单调队列就能维护，会 exkmp 就能线性；
否则可以二分 + 哈希多个 log，后面也有理由偷懒用优先队列了。
#include <bits/stdc++.h>
const int p = 31;
const int mod = 998244353;
int main() {
std::freopen("laozi.in", "r", stdin);
std::freopen("laozi.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::string s;
std::cin >> s;
int n = (int)s.length(), t1, t2;
std::vector<long long> h(n + 1), base(n + 1);
std::vector<int> a(n + 1), t0(27), z(n + 1), r(n + 1);
base[0] = 1ll;
for (int i = 1; i <= n; ++i) {
a[i] = s[i - 1] - 'a' + 1;
h[i] = (h[i - 1] * p + a[i]) % mod;
base[i] = base[i - 1] * p % mod;
}
auto gethash = [&](int l, int r) {
return (h[r] - h[l - 1] * base[r - l + 1] % mod + mod) % mod;
};
for (int i = 1; i <= n; ++i)
for (int l = 1, r = std::min(i - 1, n - i + 1), mid; l <= r; ) {
mid = (l + r) >> 1;
if (gethash(1, mid) == gethash(i, i + mid - 1))
z[i] = mid, l = mid + 1;
else
r = mid - 1;
}
for (int i = 1; i < n; ++i)
r[i] = i + std::min(i, z[i + 1]);
for (int i = 1; i <= 26; ++i)
std::cin >> t0[i];
std::cin >> t1 >> t2;
std::vector<long long> f(n + 1);
std::priority_queue<std::pair<long long, int> > q;
for (int i = 1; i <= n; ++i) {
f[i] = f[i - 1] + t0[a[i]];
for (; !q.empty() && r[q.top().second] < i; q.pop());
if (!q.empty())
f[i] = std::min(f[i], t1 - q.top().first - (long long)t2 * i);
if (i != n)
q.emplace(-(f[i] + 2ll * t2 * i), i);
}
std::cout << f[n] << '\n';
return 0;
}D. 非攻
http://222.180.160.110:61235/contest/6462/problem/4
给定 \(n\)，对于一个 \(1\sim n\) 的排列，使用最小的交换次数使得其单增。在该前提下，定义代价为每次交换的两个数之积。对于所有 \(n!\) 个排列，计算最小代价之和。
\(n\le 10^7\)。
转化成，把 \(1\sim n\) 分成无标号的若干组，每组的代价是 最小值 \(\times\) 其他元素的和，还有一个项链问题的系数，发现组间的符号是求和，考虑计算贡献。
枚举 \(i,j\) 并钦定两个同属一个环，且 \(i\) 为最小值，枚举环大小 \(s+2\)，那么有：
\[ \begin{aligned} res&=\sum_{i=1}^{n-1}\sum_{j=i+1}^n i\cdot j \cdot \sum_{s=0}^{n-i-1}\binom{n-i-1}s \cdot (s+1)!\cdot (n-s-2)!\\ &=\sum_{i=1}^{n-1}i\cdot \dfrac {(i+n+1)(n-i)}2 \cdot \sum_{s=0}^{n-i-1}\binom{n-i-1}s\cdot (s+1)!\cdot (n-s-2)!\\ &=\frac 12\times\sum_{i=1}^{n-1}i\cdot (i+n+1)\cdot (n-i)!\cdot\sum_{s=0}^{n-i-1}\dfrac {(s + 1)\cdot (n-s-2)!}{(n-i-1-s)!}\\ \end{aligned} \]
令 \(T=n-i-1\)，发现我们需要快速计算 \(f_T=\sum\limits_{i=0}^T \dfrac{(i+1)\cdot (n-i-2)!}{(T-i)!}\)。记 \(m=n-2\)，变形得 \(f_T=(m-T)!\cdot \sum\limits_{i=0}^{T} (i+1) \binom{m-i}{m-T}\)，发现似乎可以简化，令 \(k=m-T,t=T+1\)，则 \(f_T=\sum\limits_{i=1}^T i\cdot \binom {k+t-i}k\)。
然后是经典的组合意义保平安环节，即从 \(k+t\) 个有标号小球中选择一条分界线，分界线左边选一个球、右边选 \(k\) 个球的方案数。发现分界线的存在很诡异，故用分界线后方的第一个球代替，在 \(t+1\) 处新建一个虚球，规定在前 \(t+1\) 个球中选两个球，并令后一个为分界线，且令前 \(t+1\) 个中的其他球为实球，就能建立双射。在分界线后再选 \(k\) 个球，容易发现直接在范围内选 \(k+2\) 个球就能满足条件，故 \(f_T=(n-T-2)!\cdot \binom{t+k+1}{k+2}\)。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("mozi.in", "r", stdin);
std::freopen("mozi.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<long long> fac(n + 1), inv(n + 1), f(n + 1);
fac[0] = inv[0] = 1ll;
for (int i = 1; i <= n; ++i)
fac[i] = fac[i - 1] * i % mod;
auto qkp = [&](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[n] = qkp(fac[n], mod - 2);
for (int i = n - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
int m = n - 2;
for (int T = 0; T <= n - 2; ++T) {
int k = m - T, t = T + 1;
f[T] = C(t + k + 1, k + 2) * fac[m - T] % mod;
}
auto res = 0ll;
for (int i = 1; i <= n - 1; ++i)
(res += (long long)i * (i + n + 1) % mod * fac[n - i] % mod * f[n - i - 1] % mod) %= mod;
std::cout << res * inv[2] % mod << '\n';
return 0;
}C - Destruction of Walls
https://atcoder.jp/contests/arc203/tasks/arc203_c
D - Insert XOR
https://atcoder.jp/contests/arc203/tasks/arc203_d
A - 记忆
https://ac.nowcoder.com/acm/problem/274793
需要意识到问题是静态的，并且不能用线段树之类维护；故考虑离线下来，想办法在 LCA 处统计答案。
这个时候发现需要合并子树状态、整体异或、整体 +1，很容易想到 Trie。把 \(u\to\) LCA 的答案保存在 LCA 处，然后再用 DFS + 回溯统计 LCA \(\to v\) 的答案。想了半天没想到把上下拆开来做也是神了 😅
可能比较考验对字典树的理解？做个比喻，字典树的 id 就相当于对这个点上信息的『引用』。
字典树合并的时候可以考虑回收废弃点，不然可能有点卡。
#include <bits/stdc++.h>
const int X = 50;
const int maxn = 2e7 + 5;
long long d[maxn];
int tot, T[maxn][2], f[maxn], fa[maxn];
#define lc(p) T[p][0]
#define rc(p) T[p][1]
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
int newnode(void) {
int p = ++tot;
assert(p < maxn);
d[p] = lc(p) = rc(p) = 0, f[p] = p;
return p;
}
void pushdown(int p) {
if (d[p]) {
if (d[p] & 1)
std::swap(lc(p), rc(p));
d[p] >>= 1;
if (lc(p))
d[lc(p)] ^= d[p];
if (rc(p))
d[rc(p)] ^= d[p];
d[p] = 0;
}
return;
}
int ins(int p, long long x) {
for (int i = 0; i < X; ++i) {
pushdown(p);
if (!T[p][(x >> i) & 1]) {
T[p][(x >> i) & 1] = newnode();
fa[T[p][(x >> i) & 1]] = p;
}
p = T[p][(x >> i) & 1];
}
return p;
}
void merge(int &p, int q) {
if (!q)
return;
if (!p) {
p = q;
return;
}
pushdown(p), pushdown(q);
fa[lc(q)] = p, fa[rc(q)] = p;
merge(lc(p), lc(q)), merge(rc(p), rc(q));
assert(f[p] == p), assert(f[q] == q), f[q] = p;
return;
}
long long ask(int p) {
std::vector<int> st;
for (int i = 0, j = p; i < X; ++i)
st.push_back(fa[j]), j = fa[j];
for (int i = 0; i < X; ++i)
pushdown(st.back()), st.pop_back();
long long x = 0;
for (int i = 0; i < X; ++i) {
x = x * 2 + (p == rc(fa[p]));
p = fa[p];
}
return x;
}
void add(int p) {
for (int i = 0; p && i < X; ++i) {
pushdown(p);
std::swap(lc(p), rc(p));
p = lc(p);
}
return;
}
void del(int p) {
for (int i = 0; p && i < X; ++i) {
pushdown(p);
std::swap(lc(p), rc(p));
p = rc(p);
}
return;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<int> siz(n + 1), son(n + 1), top(n + 1), fa(n + 1), dep(n + 1);
std::function<void(int)> DFS = [&](int x) {
siz[x] = 1;
for (auto i : g[x])
if (i != fa[x]) {
dep[i] = dep[x] + 1;
fa[i] = x, DFS(i);
siz[x] += siz[i];
if (siz[i] > siz[son[x]])
son[x] = i;
}
return;
};
DFS(1);
DFS = [&](int x) {
if (son[x])
top[son[x]] = top[x], DFS(son[x]);
for (auto i : g[x])
if (i != son[x] && i != fa[x])
top[i] = i, DFS(i);
return;
};
top[1] = 1, DFS(1);
auto askLCA = [&](int x, int y) {
for (; top[x] != top[y]; x = fa[top[x]])
if (dep[top[x]] < dep[top[y]])
std::swap(x, y);
return dep[x] < dep[y] ? x : y;
};
struct node { long long x; int u, v; };
std::vector<node> q(m + 1);
std::vector<int> id(m + 1);
std::vector<long long> res(m + 1), ans(m + 1);
std::vector<std::vector<int> > up(n + 1), dn(n + 1), ed(n + 1);
for (int i = 1, x, u, v; i <= m; ++i) {
std::cin >> x >> u >> v;
q[i] = { x, u, v };
up[u].push_back(i), dn[askLCA(u, v)].push_back(i), ed[v].push_back(i);
}
std::vector<int> rt(n + 1);
DFS = [&](int x) {
rt[x] = newnode();
for (auto i : g[x])
if (i != fa[x]) {
DFS(i);
merge(rt[x], rt[i]);
}
add(rt[x]);
for (auto i : up[x])
id[i] = ins(rt[x], q[i].x);
d[rt[x]] ^= a[x];
for (auto i : dn[x])
res[i] = ask(find(id[i]));
return;
};
DFS(1);
tot = 0, rt[0] = newnode();
std::fill(id.begin() + 1, id.end(), 0);
DFS = [&](int x) {
d[rt[0]] ^= a[x];
for (auto i : dn[x])
id[i] = ins(rt[0], res[i]);
for (auto i : ed[x])
ans[i] = ask(id[i]);
add(rt[0]);
for (auto i : g[x])
if (i != fa[x])
DFS(i);
del(rt[0]);
d[rt[0]] ^= a[x];
return;
};
DFS(1);
for (int i = 1; i <= m; ++i)
std::cout << ans[i] << '\n';
return 0;
}B - ビーバーの会合 2 (Meetings 2)
https://www.luogu.com.cn/problem/AT_joisc2021_j
定义所求点为『局部重心』；类似树的重心，容易发现当关键点数量为奇时，只存在一个局部重心；否则，局部重心组成一条链。
即对于每一个 \(i\)，需要找到一条最长链，使得其两端存在大小为 \(i\) 的子树（容易发现取后缀 max 即可得到真实答案）。使用点分治，精细实现容易做到 \(O(n\log n)\)。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<int> mx(n + 1), siz(n + 1), p, tag(n + 1), res(n + 1, 1);
std::function<void(int, int)> DFS1 = [&](int x, int fa) {
p.push_back(x);
siz[x] = 1, mx[x] = 0;
for (auto i : g[x])
if (!tag[i] && i != fa) {
DFS1(i, x);
siz[x] += siz[i];
mx[x] = std::max(mx[x], siz[i]);
}
return;
};
auto findrt = [&](int x) {
p.clear(), DFS1(x, -1);
int n = (int)p.size();
for (auto i : p)
if (mx[i] <= n / 2 && n - siz[i] <= n / 2)
return i;
assert(0);
return -1;
};
struct node {
int u1, u2, id1, id2;
node(): u1(0), u2(0), id1(0), id2(0) {}
void upd(int u, int id) {
if (id1 == id)
u1 = std::max(u1, u);
else if (u >= u1)
u2 = u1, id2 = id1, u1 = u, id1 = id;
else if (u >= u2)
u2 = u, id2 = id;
return;
}
};
std::vector<node> s(n + 1);
std::function<void(int, int, int, int)> DFS2 = [&](int x, int fa, int dep, int anc) {
s[siz[x]].upd(dep, anc);
for (auto i : g[x])
if (!tag[i] && i != fa)
DFS2(i, x, dep + 1, anc);
return;
};
std::function<void(int, int, int, int)> DFS3 = [&](int x, int fa, int dep, int anc) {
int v = ((s[siz[x]].id1 == anc) ? s[siz[x]].u2 : s[siz[x]].u1);
res[2 * siz[x]] = std::max(res[2 * siz[x]], dep + 1 + v);
for (auto i : g[x])
if (!tag[i] && i != fa)
DFS3(i, x, dep + 1, anc);
return;
};
std::function<void(int)> DFS = [&](int x) {
x = findrt(x), p.clear(), DFS1(x, -1);
// printf("rt = %d\n", x);
for (auto i : g[x])
if (!tag[i])
DFS2(i, x, 1, i);
for (int i = siz[x] - 1; i; --i) {
s[i].upd(s[i + 1].u1, s[i + 1].id1);
s[i].upd(s[i + 1].u2, s[i + 1].id2);
}
for (auto i : g[x])
if (!tag[i])
DFS3(i, x, 1, i);
tag[x] = 1;
for (int i = 1; i < siz[x]; ++i)
s[i] = node();
for (auto i : g[x])
if (!tag[i])
DFS(i);
return;
};
DFS(1);
for (int i = (n >> 1) * 2; i; --i)
if (i + 2 <= n)
res[i] = std::max(res[i], res[i + 2]);
for (int i = 1; i <= n; ++i)
std::cout << res[i] << '\n';
return 0;
}C - The Closest Pair
https://ac.nowcoder.com/acm/problem/262593
常规方法：考虑支配对，对于每个 \(a_i\)，找到所有合法的 \(a_j\)。容易想到枚举 \(a_i\div a_j\) 来做；假设存在 \(a_k\div a_i=a_j\div a_i\) 且 \(k>j\)。
不妨设 \(a_j=K\cdot a_i+p,a_k=K\cdot a_i+q\)，\((a_i,a_j),(a_i,a_k)\) 均合法当且仅当下列条件全部成立：
- \(a_j\bmod a_i>a_k\bmod a_i\)； 则 \(a_j>a_k\)。
- \(a_j\bmod a_k>a_k\bmod a_i\)；又 \(p-q\ge a_j\bmod a_k\)（太牛了这一步），即 \(p-q>q\iff p>2q\)。
证得只关心同一个 \(a_j\div a_i\) 时的支配对数量为 \(\log n\) 级别；总对数 \(O(n\log n\ln n)\)。离线下来扫描线就行了。
对着 单点修改 区间最值 想了 1h 的单 log 做法 😰 果然小脑掉线太可怕了，第二天早上重置大脑 1s 发现自己是斯波 😓
#include <bits/stdc++.h>
const int LEN = (1 << 20);
int nec(void) {
static char buf[LEN], *p = buf, *e = buf;
if (p == e) {
e = buf + fread(buf, 1, LEN, stdin);
if (e == buf) return EOF;
p = buf;
}
return *p++;
}
bool read(int &x) {
x = 0;
bool f = 0;
char ch = nec();
while (ch < '0' || ch > '9') {
if (ch == EOF) return 0;
if (ch == '-') f = 1;
ch = nec();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = nec();
}
if (f) x = -x;
return 1;
}
void print(int x) {
if (x < 0)
putchar('-'), x = -x;
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
return;
}
void print(int x, char ch) {
print(x), putchar(ch);
return;
}
const int maxn = 4e6 + 5;
struct { int l, r, u[2]; } t[maxn];
#define lt (t[p].l)
#define rt (t[p].r)
int tot[2];
void add(int &p, int l, int r, int x, int v, int i) {
if (!p)
p = ++tot[i], t[p].u[0] = -1, t[p].u[1] = 0x3f3f3f3f;
if (i == 0)
t[p].u[0] = std::max(t[p].u[0], v);
else
t[p].u[1] = std::min(t[p].u[1], v);
if (l == r)
return;
int mid = (l + r) >> 1;
if (x <= mid)
add(lt, l, mid, x, v, i);
else
add(rt, mid + 1, r, x, v, i);
return;
}
int ask(int p, int l, int r, int ql, int qr, int i) {
if (!p || (ql <= l && r <= qr))
return t[p].u[i];
int mid = (l + r) >> 1;
if (qr <= mid)
return ask(lt, l, mid, ql, qr, i);
if (ql > mid)
return ask(rt, mid + 1, r, ql, qr, i);
if (i == 0)
return std::max(ask(lt, l, mid, ql, qr, 0), ask(rt, mid + 1, r, ql, qr, 0));
return std::min(ask(lt, l, mid, ql, qr, 1), ask(rt, mid + 1, r, ql, qr, 1));
}
#undef lt
#undef rt
int main() {
#ifndef ONLINE_JUDGE
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
const int m = 1e6;
int rt[2] = { 0 }, n;
t[0].u[0] = -1, t[0].u[1] = 0x3f3f3f3f;
read(n);
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
read(a[i]);
std::vector<std::vector<std::pair<int, int> > > t(n + 1);
for (int i = 1; i <= n; ++i) {
if (i != 1) {
for (int K = a[i]; K <= m; K += a[i]) {
for (int mx = std::min(a[i] - 1, m - K); ; ) {
int k = ask(rt[0], 1, m, K, K + mx, 0);
if (k == -1)
break;
t[i].emplace_back(k, a[k] - K);
if (k == 1 || !(a[k] - K))
break;
mx = (a[k] - K - 1) / 2;
}
}
}
add(rt[0], 1, m, a[i], i, 0);
}
for (int i = n; i; --i) {
if (i != n)
for (int K = a[i]; K <= m; K += a[i])
for (int mx = std::min(a[i] - 1, m - K); ; ) {
int k = ask(rt[1], 1, m, K, K + mx, 1);
if (k == 0x3f3f3f3f)
break;
t[k].emplace_back(i, a[k] - K);
if (k == n || !(a[k] - K))
break;
mx = (a[k] - K - 1) / 2;
}
add(rt[1], 1, m, a[i], i, 1);
}
int q;
read(q);
std::vector<int> res(q + 1);
std::vector<std::vector<std::pair<int, int> > > u(n + 1);
for (int i = 1, l, r; i <= q; ++i) {
read(l), read(r);
if (l > r)
std::swap(l, r);
u[r].emplace_back(l, i);
}
std::vector<int> bit(n + 1, 0x3f3f3f3f);
auto lowbit = [&](int x) { return x & -x; };
auto add = [&](int x, int v) {
for (; x <= n; x += lowbit(x))
bit[x] = std::min(bit[x], v);
return;
};
auto ask = [&](int x) {
auto res = 0x3f3f3f3f;
for (; x; x -= lowbit(x))
res = std::min(res, bit[x]);
return res;
};
for (int r = 1; r <= n; ++r) {
for (auto [l, v] : t[r])
add(n - l + 1, v);
for (auto [l, i] : u[r])
res[i] = ask(n - l + 1);
}
for (int i = 1; i <= q; ++i)
print(res[i], '\n');
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}求支配对的过程也要带 log（线段树），再加上扫描线的 3log，总共是常数比较大的 3log（卡了一个上午的常也是有了）。所以接下来讲解另一种奇技淫巧。
暴力分治：注意到对于比较长（\(len> B\)）的区间，答案比较小；故考虑分治。
- 对于长询问（\(len>B\)），从小到大枚举答案并 check；预处理某个范围（\(V\)）内的 \(res\) 出现的所有位置，平衡的时候还要算上调和级数和 bit。
- 对于短询问（\(len\le B\)），发现每次区间内暴力是 \(O(B^2q)\) 的；把询问离线下来，精细实现，利用询问的公共部分使得每一对数只被枚举一次就能达到 \(O(B^2 + Bq)\)。
最优解取 \(B=333,V=483\)，不自己实现一遍了。
D - 仙人掌
https://www.luogu.com.cn/problem/P3687
把边双从图中删除、问题转化为树上边不交的链覆盖，使得所有链长 \(\ge 2\) 的方案数。发现由于边可以不被覆盖，常规 DP 会使得在父节点处合并时需要额外的数量维，参考树上背包，复杂度 \(O(n^2)\)。
思考时会注意到两个限制可以抵消——如果认为长为 \(1\) 的链就是不被覆盖的边，覆盖所有树边，显然可以建立和合法解的双射。此时合并是非常方便的，注意到每个儿子的系数一定都参与『分步』，只需要求出『分类』的系数。这个可以预处理（和 二分图染色 这个题有点像），令 \(f_i\) 表示一个点度数为 \(i\) 时的答案，参考错排的思路，则 \(i\) 可以不参与配对，也可以乱选一个点配对，如果选中了已配对的点就令其和 \(i-1\) 交换，可以建立和合法解的双射。则 \(f_i=f_{i-1}+(n-1)f_{i-2}\)。
首先需要 check 原图是否为仙人掌，顺带回忆一下连通性的知识——在 DFS 树上差分，检查是否有边被覆盖两次即可。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > g1(n + 1);
for (int x, y; m--; ) {
std::cin >> x >> y;
g1[x].push_back(y), g1[y].push_back(x);
}
bool flag = 1;
int now = 0, cnt = 0;
std::vector<int> st, dfn(n + 1), low(n + 1), col(n + 1), diff(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
st.push_back(x);
dfn[x] = low[x] = ++now;
for (auto i : g1[x])
if (!dfn[i]) {
// printf("x = %d, %d -> %d\n", x, x, i);
DFS(i, x);
diff[x] += diff[i];
// printf("x = %d, diff[%d] += diff[%d]\n", x, x, i);
low[x] = std::min(low[x], low[i]);
}
else if (i != fa && dfn[i] < dfn[x]) {
low[x] = std::min(low[x], dfn[i]);
++diff[x], --diff[i];
// printf("x = %d, ++diff[%d], --diff[%d]\n", x, x, i);
}
if (diff[x] >= 2)
flag = 0;
// printf("x = %d, diff[%d] = %d\n", x, x, diff[x]);
if (low[x] == dfn[x]) {
++cnt;
for (int p = -1; p != x; ) {
p = st.back(), st.pop_back();
col[p] = cnt;
}
}
return;
};
DFS(1, -1);
if (!flag) {
std::cout << 0 << '\n';
continue;
}
std::vector<std::vector<int> > g(n + 1);
for (int i = 1; i <= n; ++i)
for (auto j : g1[i])
if (col[i] != col[j])
g[i].push_back(j);
std::vector<long long> f(n + 1), dp(n + 1);
dp[0] = 1ll, dp[1] = 1ll;
for (int i = 2; i <= n; ++i)
dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % mod;
std::vector<int> tag(n + 1);
DFS = [&](int x, int fa) {
f[x] = 1ll, tag[x] = 1;
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
(f[x] *= f[i]) %= mod;
}
(f[x] *= dp[(int)g[x].size()]) %= mod;
return;
};
auto res(1ll);
for (int i = 1; i <= n; ++i)
if (!tag[i])
DFS(i, -1), (res *= f[i]) %= mod;
std::cout << res << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}E. Many Minimizations 是数学题，跳了。
F - 对数据结构的爱
https://www.luogu.com.cn/problem/P5609
线段树做法：考虑线段树维护函数。定义 \(f(x)\) 表示区间上想要减去 \(x\) 次 \(p\) 需要的最小初始值（这样才能让定义域和区间长有关），查询时直接二分即可；考虑初始化时如何合并。
首先思考较为暴力的做法，对于左侧点 \(a\) 和右侧点 \(b\)，若 \(f(a+1)-1+s_l-a\cdot p\ge f(b)\)，也即可以减去 \(a+b\) 次，就可以用 \(\max(f(a),f(b)-s_l+a\cdot p)\) 来更新 \(f(a+b)\)。
发现 \((a,b)\) 的贡献一定小于 \((a+1,b-1)\) 的贡献；具体地，发现 \(f(x+1)-f(x)\ge p\) 后就很显然了。采用双指针，优先移动 \(b\)，就能把最短区间扫一遍。
分治做法：Ast 自己还没切，蹲一个 sol。
无名题
背景：给定 \(n,k\)，对于 \(\forall\, 1\le i\le n\)，令 \(a_i=i\bmod k\)，问一共有多少个本质不同的子序列？对于 \(k=1,2,\cdots,n\) 分别求出答案。