游记 - GDKOI 2023 提高组

膜拜学长。

DAY 0

2023.3.11.

简要题意：

T1：判断两个 $n\times n$ 矩阵乘积是不是第三个矩阵。多测，$\sum n\le 3000$。模意义下。

T2：求 $1\sim n$ 的错排中满足前 $m$ 位的值 $> m$ 的排列数目。$T,n\le 2\times 10^5$，$0\le m\le n$。模意义下。

T3：给一个图，给每个点赋权值，满足每个权值不超过这个点的限制，邻点值不同，且全部权值的异或和是给定的。$n\le 15$，$m\le \frac{n(n-1)}{2}$，权值 $\le 10^{18}$。模意义下。

果断写了 T1 判断每行每列之和和对角线相等的乱搞，和 T2,3 的暴力。还有两个半小时，睡觉，推不出来。

出来之后发现人均善于 T1 随机撒点，T2 人人会 dp/容斥，裂开。

T1 正解是把 $A\times B=C$ 写成 $v\times A\times B=v\times C$，生成一些一维向量 $v$。于是觉得我可能要挂。不过有无人 hack 我的做法？

T2 是从递推式出生成函数，T3 是数位 dp、容斥、从按边容斥到按联通块容斥。听不懂。

下午又来了大学讲座、企业广告，“把我们的一生都安排好了是吧”。

本来说滚榜发成绩，咕咕咕了，好像是有人每次测评结果都不一样。

DAY 1

2023.3.12.

T1：给一棵树，每次询问在树上找到三个点 $x,y,z$，满足两两之间的距离是给定的数。$n,q\le 2\times 10^5$。

T2（名字叫做“马戏团里你最忙”，当然是形容我啦）：给一个初始的数，每次均匀从 $[0,2^n)$ 里面选一个数，$p$ 的概率进行 $\texttt{OR}$ 操作，$1-p$ 的概率进行 $\texttt{AND}$ 操作，总共 $k$ 次操作，权值和是每次的 $c_x$，$x$ 表示当前的数，$c$ 是一个给定的数组。最后输出每个终点对应的权值和期望。$n\le 17$，$k\le 10^9$。模意义下。

T3：给一棵树，每次询问 $x$ 的子树中和 $x$ 的距离 $d(x,y)<k$ 的 $\sum_y v_y\oplus d(x,y)$，算边数。$n,q\le 10^6$。

想象一下：自己本来算出可以拿到 $150+$ 的部分分，越推越发现其实也就 $90$ 的部分分。T2 甚至完全没部分分下手。T1 就直径+$O(nq)$ 暴力，听天由命。

出场一看：T1 这不明显的三维偏序，我干嘛。T2 有巨佬会 FWT，说是高维前缀和。我不会。

解法上，T2 好像是神秘矩阵快速幂。T3 讲题画的图好像是说：在 bfs 序上每次询问同一深度都在同一段上，所以最后可以长得很像前缀和。好像又可以长链剖分，可是长链剖分我不仅不会，甚至是 T1 想到的长链剖分。

结果

$100+20+20+70+0+20=230$，Ag。

无功无过。只是硬实力就这个鬼样。有点疑惑怎么 D2T1 少了 $10$ 分，不过 D2T3 比预期多了 $10$ 分，都可以接受。

Ag 线 $190$，Au 线 $260$。

还有什么好说的呢？磕多项式、概率、树论，这些让人望而生畏的总是要磕。

好多那么厉害的人，为什么都写挂。不过他们有可做的解，暴力那是连写挂的余地都没了。

憋屈的是这几天睡眠老是不足，就是想晚睡，情绪也比较低落。要调整了。