目录
写在前面
补题地址：vjudge。
以下按照场上过题顺序排序。
首银。
比游记更早出来，没想到吧。
游记链接：留坑。
A
场上先开的这道。
直觉是考虑先全部区间加直到最小值，然后将非最小值全单点加，再重复上述过程。然而会被递增序列卡掉。
瓶颈在于单点加太多了。大神 dztlb 手玩了几分钟发现可以对目标的值域二分，对于某个值域区间，先对后一半每个位置先做单点加，然后对后一半区间加直到后一半的最小值，然后再递归处理前后两半。
然后我就上机开写了，调的时候慢了几分钟呃呃，幸好在 Nebulyu 指导下一发过了。
F
真签到。
枚举所有环边检查删边后节点度数，有度数大于等于 5 的点则贡献为 0，否则贡献为 \(n\) 减去度数为 4 的点。
我在写 A 的时候 dztlb 和 Nebulyu 出的思路，我下机之后 dztlb 上机开写，稍微调了下一发过了。
场下也是一发过了呃呃。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const int kM = 2e5 + 10;
//=============================================================
int n;
int edgenum, head[kN], v[kM], ne[kM];
int into[kN], into1[kN], num4, num5, num6;
bool incircle[kN];
LL ans;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void Topsort() {
std::queue <int> q;
for (int i = 1; i <= n; ++ i) {
if (into[i] == 1) q.push(i);
}
while (!q.empty()) {
int u_ = q.front(); q.pop();
incircle[u_] = false;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if ((--into[v_]) == 1) q.push(v_);
}
}
}
int check(int u_, int v_) {
if (num6) return 0;
if (into1[u_] == 5) -- num5, ++ num4;
if (into1[u_] == 4) -- num4;
if (into1[v_] == 5) -- num5, ++ num4;
if (into1[v_] == 4) -- num4;
int ret = num5 ? 0 : n - num4;
if (into1[u_] == 5) ++ num5, -- num4;
if (into1[u_] == 4) ++ num4;
if (into1[v_] == 5) ++ num5, -- num4;
if (into1[v_] == 4) ++ num4;
return ret;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
n = read();
for (int i = 1; i <= n; ++ i) incircle[i] = true;
for (int i = 1; i <= n; ++ i) {
int u_ = read(), v_ = read();
Add(u_, v_), Add(v_, u_);
into[u_] ++, into[v_] ++;
into1[u_] ++, into1[v_] ++;
}
for (int i = 1; i <= n; ++ i) {
if (into[i] == 4) ++ num4;
if (into[i] == 5) ++ num5;
if (into[i] >= 6) ++ num6;
}
Topsort();
for (int u_ = 1; u_ <= n; ++ u_) {
if (!incircle[u_]) continue;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (u_ > v_ || !incircle[v_]) continue;
ans += check(u_, v_);
}
}
printf("%lld\n", ans);
return 0;
}
G
dztlb 写 F 的时候开了这道，一看 \(k\le 10\) 给我笑烂了哈哈
首先预处理所有串的哈希值，对于每次询问都枚举所有串并检查，检查时不断地通过哈希+二分求得第一个不同的位置即可。
F 写完之后我上机开写，场上一发过了，写完直接怪叫了一声，太激动了。
现在才刚过去一个多小时，这个时候看了眼名次我草三十多，一发罚时都没有，感觉至少银是相当稳了，甚至还有希望——
真的如此吗？
L
那么问题来了，直到现在都是我和 dztlb 在写，Nebulyu 在干什么呢？
时间回到我在写 A 的时候，期间一直在看榜，发现 L 过的数量仅次于 A，并且全都是一发过的。然而是期望，我的数学一直是一拖四于是丢给了 Nebulyu。
Nebulyu 首先考虑求 \(f_{i, j}\) 表示第 \(i\) 次生长时还可以生儿子的深度为 \(j\) 的节点的数量，于是有了一个 \(O(k^2)\) 的 DP，然而优化不了，于是寄。一直推到我写完 G 的时候出了一个好像是斯特林数的思路，于是开始大力推式子，代码也很有思路了于是上机了。这个时候 I 过了不少也，我在写的时候他们开了 I 但是没什么想法于是我就去开了 I。
然后 L 就卡住了呃呃，又推了 1h 多发现斯特林数的思路是假的，跑出来的和手动打表出来的对不上，陷入僵局。这个时候 I 出来了，需要去抄一个 Pollard_Rho 于是我就先上去开写了。
在我写 I 的时候 dztlb 突然灵机一动相当了另一种思路，然后推了下发现超级可行而且比我那逼泼辣的肉好写多了，于是开冲！
大力写了一发发现被卡常了，改线性求逆元之后一发过了，赢！
此时距离封榜没多少时间了，这个时候的排名加上打星是五十多，还在银线内，而且手里还有一道题马上就出来了，感觉至少银是稳了，激动人心！
然后下面是补题。
考虑记第 \(i\) 轮加点后所有节点深度和为 \(f_i\)，显然每轮 \(f\) 的增量与树的实际形态是无关的，仅需考虑第 \(i\) 次添加的结点 \(D_i\) 的深度，即有：
\[f_k = f_{k-1} + M\times E(D_k) = M\times \sum_{i=1}^k E(D_i) \]\(E (D_i)\) 取决于被选出的结点的深度。手玩发现另一个显然的性质是每轮中叶节点的数量是固定的，第 \(i\) 轮加点后的叶节点数量即为 \((M-1)\times i + 1\)。记第 \(i\) 轮加点后所有叶节点的集合为 \(P_i\)，则有：
\[E(D_i) = \dfrac{E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u)\right)}{(M-1)(i-1) + 1} + 1 \]对于上式的分子考虑递推，即考虑从 \(P_{i-1}\) 中选出某个点进行生长来得到 \(P_i\)，设被选出的点深度为 \(d\) 则有：
\[\begin{aligned} E\left(\sum\limits_{u\in P_{i}} \operatorname{dep}(u)\right) &= E\left( \left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u)\right) - d + M(d + 1) \right)\\ &=E\left( \left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u)\right) +(M-1) d + M \right)\\ &=E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u) \right) + (M-1)E\left( d\right) + M \end{aligned}\]然后考虑 \(E(d)\) 的实际意义，即从 \(P_{i-1}\) 中选出一个节点的期望深度，则有：
\[\begin{aligned} E\left(\sum\limits_{u\in P_{i}} \operatorname{dep}(u)\right) &=E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u) \right) + (M-1)E\left( d\right) + M\\ &= E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u) \right) + \frac{M-1}{(M-1)(i-1)+1}E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u) \right) + M\\ &=\dfrac{(M-1)i + 1}{(M-1)(i-1) + 1}E\left(\sum\limits_{u\in P_{i-1}} \operatorname{dep}(u) \right) + M \end{aligned}\]记 \(g_i = E\left(\sum\limits_{u\in P_{i}} \operatorname{dep}(u)\right)\)，则有：
\[\begin{aligned} g_i &= \dfrac{(M-1)i + 1}{(M-1)(i-1) + 1}g_{i - 1} + M \end{aligned}\]答案即：
\[f_k = M\times \sum_{i=0}^{k-1}\left( \dfrac{g_i}{(M-1)(i-1) + 1} +1\right) \]预处理下逆元复杂度 \(O(K)\) 级别。
场上似乎不是这个推法，必须每次对分母再求个逆元，复杂度是 \(O(k\log p)\) 但卡了卡常之后也跑过去了。
I
时间回到 Nebulyu 在大战斯特林数的时候。
首先是 dztlb 发现 \(k>4\) 时 \(a\) 和 \(b\) 的上界很小，因为当 \(k\) 较大时非常容易出现 \(a^k - (a-1)^k >n\) 从而导致没有整数解，于是此时可以移个项变成 \(a^k = b^k + n\)，枚举 \(b\) 之后二分检查是否存在 \(a\) 使得方程有解。
对于 \(k=3\) 的情况，考虑立方差公式有 \(a^3 - b^3 = (a-b)(a^2 + ab + b^2) = n\)，考虑枚举 \(n\) 的因子 \(d\)，则有：
\[\begin{cases} a - b = d\\ a^2 + ab + b^2 = \frac{n}{d} \end{cases}\]大力求根公式判断是否有正整数解即可。
对于 \(k=4\) 的情况考虑平方差公式，同样考虑枚举 \(n\) 的因子，有：
\[\begin{cases} a^2 - b^2 = d\\ a^2 + b^2 = \frac{n}{d} \end{cases}\]同样大力求解判断是否有正整数解即可。
用计算器玩了下发现 \(n\le 10^{18}\) 的因数也就是 \(10^5\) 级别，然后问题是如何枚举 \(n\) 的所有因数。没想到什么很好的方法，然后我脑子一抽，那就大力 Pollard_Rho 质因数分解 + dfs 枚举质因数次数就好了哈哈我草
于是开始翻 OI-wiki，发现 Pollard_Rho 才 \(O(n^{\frac{1}{4}})\) 并且在 \(10^{18}\) 内可以保证是超大概率正确的，于是开抄！
此时是以 L 优先的双线开题，过了 L 之后也几乎写好了，写了将近两百行妈的。
调的时候送午饭来了，一人一瓶 500cc 的可口+双层鸡排堡我草，tama 的 Nebulyu 和 dztlb 在我旁边吃汉堡我他妈调题，这下成代码黑奴了，调到后面精神状态不太好了，甚至开始拆米浴了妈的。
发现 \(k=3\) 和 \(k=4\) 的情况都写挂了妈的，改完之后把所有 LL 全换成 __int128 之后过样例了，交了一发 CE 了，发现是 sqrt 不能传入 __int128，于是强制类型转换了下一发过了。
然后开始怪叫，开始吃汉堡！
后面就摆了，看了下罚时相当优秀估计是稳银了，口了一下 DEK 发现一时半会也写不完，然后开始玩电脑看榜鉴赏逆天队名。
玩麻酱连连看的时候我绷不住了旁边队也绷不住了哈哈。
结束！
E
你以为是数据结构？错误的其实是结论提。
设 \(x,y\) 分别为出现次数 \(\operatorname{cnt}\) 最多和次多的两种颜色。
考虑一种特殊情况，设它们出现次数的最高位分别为 \(m_x, m_y\) 并且 \(m_x = m_y=m\)，则答案的上界为 \(2^{m + 1} - 1\)，并且肯定存在一种方案使得答案可以取到这个上界。至于怎么取到，考虑先选中整个序列，然后不断地从两边缩小区间，则肯定存在某个时刻使得 \(\operatorname{cnt}_x, \operatorname{cnt}_y\) 中的某一方变为 \(2^{m} - 1\)，而另一方的最高位仍然为 \(m\)，此时即可达到这个上界。
然后考虑更一般的情况，显然答案的下界为 \(\operatorname{cnt}_x \operatorname{or} \operatorname{cnt}_y\)，然后同样考虑上述不断缩小区间的过程，显然在某一时刻可以使得答案包括 \(\operatorname{cnt}_x \operatorname{or} \operatorname{cnt}_y\) 中所有为 1 的位的同时，使某一方的 \(\operatorname{cnt}\) 中 \(0\sim \operatorname{log}_2 (\operatorname{cnt}_x \operatorname{and} \operatorname{cnt}_y) - 1\) 位上全为 1，则答案的上界为 \(\operatorname{cnt}_x \operatorname{or} \operatorname{cnt}_y \operatorname{or} (2^{\operatorname{log}_2 (\operatorname{cnt}_x \operatorname{and} \operatorname{cnt}_y) - 1} - 1)\) 并且一定可以取到。
综上，答案即：
\[\operatorname{cnt}_x \operatorname{or} \operatorname{cnt}_y \operatorname{or} \left(2^{\left\lfloor\operatorname{log}_2 (\operatorname{cnt}_x \operatorname{and} \operatorname{cnt}_y)\right\rfloor - 1} - 1\right) \]//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, cnt[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
for (int i = 1; i <= n; ++ i) cnt[i] = 0;
for (int i = 1; i <= n; ++ i) {
int x = read(); ++ cnt[x];
}
std::sort(cnt + 1, cnt + n + 1);
int ans = (1 << (std::__lg(cnt[n] & cnt[n - 1]))) - 1;
printf("%d\n", cnt[n] | cnt[n - 1] | ans);
}
return 0;
}
M
K
写在最后
学到了什么：
- I：\(10^{18}\) 内的数因数数量不算多，估计也就至多 \(10^5\) 级别。
- M：超大数判相等可以考虑取模，另一个这个套路的例子：The 2021 ICPC Asia Jinan Regional Contest - J Determinant。