Solution. Good Bye 2022
这一场题目难度应该还是挺高的，而且细节很多，一共交了五发 unsuccessful submission，尤其是在 C 上浪费了很多时间，感觉这场 C 应该放在 D 后面比较合理，当然 C 如果思路正确做起来也很快，思维难度很难衡量。
E 我可以自己做出来，但是赛时时间不够，而且我也不确定就算有充足时间在没有 hack 数据的情况下我能不能把代码调对。
E. Koxia and Tree
任意两点距离的期望等价于去求任意两点之间的距离和，这启发我们去计算每条边的贡献。
事实上，每条边被计算的次数是这条边两端子树中蝴蝶数量的成绩。
不难发现，在操作这条边之前，这条边一端子树中的蝴蝶不可能跑到另一端的子树去，而当前这条边最多导致一只蝴蝶的位置发生变动，所以子树内蝴蝶数量也最多变化 $1$，我们只要动态维护每个结点上有蝴蝶的概率即可计算每条边被计算的期望次数。
具体的概率计算其实非常简单，分类讨论即可，官方题解中给出了比较简单的式子，即如果 $u$ 处有蝴蝶的概率为 $p_u$，现在对 $u$ 和 $v$ 间的边进行操作，则 $p_u,p_v\gets \dfrac{p_u+p_v}{2}$，但我目前没有对这个式子比较直观的解释，分类讨论能够得到同样的结果。
upd. https://codeforces.com/blog/entry/110754?#comment-987308
每一次操作可以理解为以 $\dfrac 12$ 的概率交换两个点的状态，即有/没有蝴蝶，这样概率很显然是 $\dfrac{p_u+p_v}2$。
Code
namespace Main{
const int N = 300005;
const int MOD = 998244353;
int n, k, inv, cnt[N], dep[N];
ll a[N];
vector<pair<int, int>> edges;
vector<int> g[N];
ll qpow(ll n, ll k){
ll res = 1;
while(k > 0){
if(k & 1) res = res * n % MOD;
n = n * n % MOD;
k >>= 1;
}
return res;
}
void dfs(int u, int fa){
dep[u] = dep[fa] + 1;
for(int v: g[u]){
if(v == fa) continue;
dfs(v, u);
cnt[u] += cnt[v];
}
}
void Main(){
inv = qpow(2, MOD - 2);
input(n, k);
for(int i = 0, u; i < k; i++){
input(u);
a[u] = 1;
cnt[u] = 1;
}
for(int i = 1, u, v; i < n; i++){
input(u, v);
edges.emplace_back(u, v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
ll ans = 0;
for(pair<int, int> e: edges){
int u = e.first, v = e.second;
if(dep[u] > dep[v]) swap(u, v);
int x = k - cnt[v], y = cnt[v];
ll p1 = a[u] * (1 - a[v] + MOD) % MOD * inv % MOD; // u -> v
ll p2 = a[v] * (1 - a[u] + MOD) % MOD * inv % MOD; // v -> u
ans = (ans + p1 * (x - 1 + MOD) % MOD * (y + 1) % MOD) % MOD;
ans = (ans + p2 * (x + 1) % MOD * (y - 1 + MOD) % MOD) % MOD;
ans = (ans + (1 - p1 - p2 + MOD + MOD) % MOD * x % MOD * y % MOD) % MOD;
ll nu = 0, nv = 0;
nv = (nv + p1) % MOD;
nu = (nu + p1 + a[u] * a[v] % MOD) % MOD;
nu = (nu + p2) % MOD;
nv = (nv + p2 + a[u] * a[v] % MOD) % MOD;
a[u] = nu, a[v] = nv;
}
write(ans * qpow(1ll * k * (k - 1) / 2 % MOD, MOD - 2) % MOD);
return;
}
} // namespaceF. Koxia and Sequence
很有意思的题目。
序列中的每个元素都是等价的，所以我们可以只考虑其中一个元素 $a_i$，若 $a_i=t$，则 $t$ 被计算的次数是「序列长度 $\times$ $a_i=t$ 时好序列的数量」，不难发现如果序列长度即 $n$ 是偶数，则最终答案一定为 $0$，否则，我们只需要让 $a_i=t$ 时好序列的数量为奇数即可。
我们要求所有 $a_i$ 或起来等于 $y$，但这个限制不好满足，这启发我们进行容斥，考虑所有 $a_i$ 或起来为 $y$ 的子集且所有 $a_i$ 和为 $x$ 的序列数量。
一个炫酷的结论是：$y$ 是 $x$ 的子集等价于 $\dbinom xy\bmod 2=1$，证明使用 Lucas 定理即可。
于是，所有 $a_i$ 或起来为 $y$ 的子集也就是所有 $a_i$ 都是 $y$ 的子集，进而满足条件的序列数量在模 $2$ 意义下可以表示为：
$$
\sum_{\sum a_i =x}\prod\binom{y}{a_i}\pmod 2
$$
而根据 Vandermonde 恒等式，我们知道这个式子等价于 $\dbinom{ny}{x}\pmod 2$，Vandermonde 恒等式很好理解，考虑组合意义即可，也就是将所有 $ny$ 个物品分为 $n$ 个部分，考虑我们在每个部分中选取了多少个物品。
这样我们也可以在固定 $a_i=t$ 时对好序列进行计数，但是这样做复杂度不能接受，我们考虑对每一个二进制位单独计算贡献即可。
注意容斥有多重可行的实现方式，可以对好序列的数量进行容斥，也可以直接对答案进行容斥，后者是在异或意义下进行的，而前者由于我们只关心数量的奇偶性，也可以放在异或意义下进行。
Code
namespace Main{
ll n, x, y;
void Main(){
input(n, x, y);
if(n % 2 == 0) return puts("0"), void();
ll ans = 0;
for(int i = y; i > 0; i = (i - 1) & y){
for(int j = 0; j < 20; j++){
if((i >> j & 1) && ((x - (1 << j)) | (n * i - (1 << j))) == n * i - (1 << j)){
ans ^= 1 << j;
}
}
}
write(ans);
return;
}
} // namespace本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
