2026联合省选 游记
省流：分数比较随机。
Day -1
本来计划复习 DS，结果打开网页的时候不小心输成了 generals.io。晚上打了会儿球，回家又不小心点开了无畏契约，最后看了会儿板子和博客，大概 23:00 睡觉了。
Day 1
考场和去年一样在石室，到考场比较晚就直接进去了，然后到位置之后开始睡觉。
开考看 T1，发现是最擅长的计数/期望类题目，将贡献拆到每个点，然后设 \(f_{u,i}\) 表示子树 \(u\) 内重链长为 \(i\) 的概率，直接转移似乎是 \(\mathcal{O}(n^3)\) 的。然后发现先做一遍背包之后，再对每个儿子做撤销背包即可，复杂度跟树上背包相同，多项式求逆需要找到第一个非零位，复杂度 \(\mathcal{O}(n^2)\)，大概写了半个多小时过了所有大样例。
然后发现 T2T3 咋全都是构造。先看 T2，没有任何头猪，然后想了会儿会了全 \(0\) 和全 \(1\) 的特殊性质，发现拓展到原问题没有任何前途。想到了 10:00，发现如果从左往右填，那么只需要记录有几个后缀一定比原串小，当前的 border 是啥以及有没有出现过原串就够了，设 \(f_{i,j,k,0/1,p}\) 表示填了 \(i\) 位，有 \(j\) 个后缀一定比原串小，border 为 \(k\)，是否出现过原串，答案能不能为 \(p\)，最后一维是 bitset。
然后发现 \(j\) 是根号级别，然后有个小剪枝就是 \(i\) 越小越好，所以直接一直转移直到不能拓出新状态，复杂度未知，最后一个大样例跑了 3.3s，得分应该是 90~100（一个比较唐的事情是我发现了 \(i\) 越小越好但是没有想到换维）。
写完 T2 已经是 12:00 了。开 T3