谁的生活不迷茫，谁的人生不迷惑。每个人都希望未卜先知，都希望掌控自己命运的罗盘，可变换莫测的世界总让我们感到失望，其实，我们的困惑并不在身外，而在我们的内心深处。我们总是希望心灵的疑惑得带一个真诚的回应，即便这个回应只是简单的“是”或“否”。——《答案之书》

引言与比赛无关，只是最近看到一段有意思的文字。

B

签到题，我要是少两发罚时，手速再快一点就好了。

A

签到题，手速还是不够快。

C

第一反应是一个组合数学，根据题意很容易写出答案就是：

$$
\sum_{i=1}^{n-1}\sum_{j=1}^{n-i}C_{n}^{i}\times C_{n-i}^{j}
$$

尝试化简这个式子，发现无从下手。于是乎转换思路，考虑递推。

对于 $f(n)$ 来说，考虑前一项如何转移。假设先选 $n-1$ 个数字，那么对于每一个可能的 $(A,B)$，$n$ 这个数字可能放入 $A$，也可能放入 $B$，也可能都不放入，这样就产生了 $3\times f(n-1)$ 的贡献。对于一个子集单独为 $\{n\}$ 的情况，显然另一个子集需要在 $n-1$ 个数里选，那么就有 $2^{n-1}-1$ 种选法，考虑到有序对，故乘 $2$。所以递推式为 $f(n)=3f(n-1)+2^n-2$，起点为 $f(1)=0$。

那么现在需要求通项公式，这里我就不会了，还是靠我队友算的。反正凑配一下就可以发现通项公式就是 $f(n)=3^{n}-2^{n+1}+1$，那么打一个快速幂就可以了。

一开始我以为这题可能是一道矩阵快速幂的题目，不过没想到直接就把通项公式求出来了。

E

看到群里的描述或许这题是被我卡常过的。我的思路是枚举 $j,k$，对于每一个 $a[j]\ XOR\ a[k]$ 用 trie 树查找最优的 $a[i]$。实际上当时超时了，把 std::vector 换成数组，然后用快读才过了。不太清楚正解是啥。

D

一眼看到这题感觉是一道非常 DP 的题目，但是一时间没有很快想到思路。赛时的时候 T 了两发 E 题，然后换队友做这题，但是队友 WA 了，于是换我来写 E，结果没想到就改了常数就过了。然后开始思考这题。

我们可以考虑 $f_i$ 表示有多少点可以到达 $i$ 点，$g_i$ 表示从 $i$ 点出发能到达多少点。那么路径可以分成三类。以 $i$ 为起点，终点和中间点。那么答案应该就是 $ans_i=f_i\times g_i+f_i+g_i+1$。（至于为什么要+1，其实我还没想明白，反正加了就对了）

考虑如何计算 $f_i$、实际上 $f_i,g_i$ 的计算方式是一致的，只不过后者是在反图上求。这里就是做一下 DP，容易看出 $f_v=\sum_{(u,v)\in G}{(f_u+1)}$。DP 的话要保证合法的顺序，所以先做一遍拓扑排序。

实际上我们需要考虑重边的情况。容易想到有几条重边，走法就会多几倍。所以只需要记录一下边出现的次数即可，最后的答案为：

$$
f_v=\sum_{(u,v)\in G}{(f_u+1)}\times cnt(u,v)
$$

F

其实我没啥思路，%一下队里 AK 的佬，我自己确实还是得训。