日记

我尽力，我无悔。

T1 # Link to T1

对于那种只输入一两个数的题，首先不要去想正解，先猜半个小时结论看看猜不猜的出来。多半是猜的出来的

可是我写 T2 去了。

发现从 $0$ 有 $\frac{1}{n}$ 的概率一发入魂。而剩下 $\frac{n - 1}{n}$ 的概率就是在 $[1,n - 1]$。对于每个点都有 $\frac{1}{n}$ 的概率赢，有 $\frac{n - 2}{n}$ 的概率留在 $[1,n - 1]$，那么对于每个 $i \in [1,n - 1]$ 都是一样的。期望是 $1 + \frac{(n - 1)^2}{n}$。

T2 # Link to T2

赛时想法：设 $dp_{i,j}$ 表示第 $i$ 个点取值为 $j$ 的方案数。显然有：$dp_{i,j} = \sum\limits_{k = 1}^{a_i}dp_{i - 1,k} \times [k \neq j]$。复杂度 $O(nV^2)$，可以通过全局和优化到 $O(nV)$，然后拿到 $20$ 的好成绩。
我们发现这玩意可以简化成三个操作：区间取反，区间赋值，区间加。前面两个都是特化的区间乘。我们直接动开线段树，花了 2h 的时间获得的 $60$ 的好成绩。

正解是这样的：正难则反。我们想要求恰好有 $0$ 个非法点的情况数，我们就尝试求钦定有 $i$ 个非法点的情况数 $F(i)$，然后反演一下得到最终的答案。

考虑如何求 $F(i)$。设 $dp_{i,j}$ 表示前 $i$ 个数分 $j$ 段的方案数。显然有 $F(i) = dp_{i,n - i}$。有显然的转移：$dp_{i,j} = \sum\limits_{k = 1}^{i}dp_{k - 1,j - 1} \times \min\limits_{l = k}^{i}a_l$。复杂度 $O(n^3)$，可以拿到 $0$ 分的好成绩。

我们发现我们不关心 $j$ 的值，只关心它的奇偶性。我们就可以每次转移都乘一个 $-1$，变成 $dp_i = \sum\limits_{k = 1}^{i}-dp_{k - 1} \times \min\limits_{l = k}^{i}a_l$。复杂度 $O(n^2)$，可以获得 $60$ 的好成绩。

最后用单调栈优化到 $O(n)$ 即可通过。

T3 # Link to T3

我们发现如果对于一个可行的方案，每个数都异或一个 $x$，最终答案也可行。且总的异或和也异或了 $y$。所以我们不用考虑具体的方案，求出总方案数除以 $2^k$ 就行。

考虑先填好第二行，方案数 $2^k \times (2^k - 1) \times (2^k - 2) \times \cdots \times (2^k - n)$，然后钦定第一行有 $i$ 个与第二行冲突，方案数为 $(2^k - i) \times (2^k - i - 1) \times (2^k - i - 2) \times \cdots \times (2^k - n + 1)$。直接反演得到恰好有 $0$ 个与之冲突的方案数。

后日谈 # Link to 后日谈

今天就是纯纯的数学题综合训练。于是开始预习复习概率与期望。

我尽力，我无悔。