Light switches注意到 $S \le 30$ ，我们考虑进行折半搜索。考虑复杂度是啥，如果所有集合操作都使用 bitset ，不难发现这里的两个开关并起来就是做个异或，那么考虑枚举一下前 $A$ 个开关的情况进行预处理，然后查询的时候对剩下的开关枚举情况，预处理的东西丢进一个 unordered_map 里（貌似 unordered_map 对 bitset 有自带的 Hash 方式），复杂度就是 $O(2^A \frac Nw + q\frac N w 2^{S-A})$ ，不难发 ...

一个我没写过的套路。 这个题目其实就是问你给你一个串，可以往前添加一些字符，往后添加一些字符，有多少种添加方式使得最终串不同。 我们先考虑向前添加字符，不难发现一个字符串向前添加字符可以得到的就是 parent 树子树内的本质不同的所有字符串。设这个串长为 $|S|$ ，子树内的本质不同串的个数为 $a$ ，当前点上最短串长为 $b$ ，那么添加方案数就是 $a+b-|S|$ 。 我们考虑往后添加字符的情况，往后添加一个字符就是在 SAM 的 DAG 往后走一步。所以如果我们设往后添加了 $k$ ...

我们按照与对角线平行的线上的数来考虑。如果只考虑在一条这样的对角线上进行操作，那么就变成了一个普通的 Nim 游戏。而如果有很多对角线，不难发现在进行一次操作的时候，这个人可以把后面的所有对角线的状态改变。 于是我们考虑找出第一个异或和不为 $0$ 的对角线，这个对角线单看是先手必胜的。考虑先手对这个对角线进行一次操作把它的异或值变为 $0$ 。要么此时已经没有数了，先手胜利。要么后手会有一些选项：选择这条对角线或之前的对角线，这样的话必然会导致一条对角线的异或和变成非 $0$ ，先手可以继续操 ...

首先，模 $2$ 就是行列式的值。 我们考虑容斥，钦定某些列没有数被选，那么有 \text{perm } A = (-1)^n \sum_{x \in \{0,1\}^n} (-1)^{x_1+x_2+\cdots +x_n} \prod _{i=1}^n (Ax)_i也就是钦定某些列不选，然后每一行任意选一个数。 由于后面有一个 $\prod$ ，也就是说一个 $x$ 会造成贡献当且仅当 $Ax$ 中 $0$ 的个数小于等于 $1$ 。 于是我们考虑 $Ax$ 由于只有最多一个位置为 ...

A Winding polygonal line神仙构造。 考虑拿凸包上一个点 $A$ ，然后每次找一个点 $B$ ，如果是 L ，则使得剩下的所有点都在 $AB$ 的左侧，然后连过去即可，否则就使得所有点都在 $AB$ 右侧。不难发现这样每一轮都一定能找到剩余点继续，且由于所有点都在一侧，显然不可能出现线段相交。 复杂度 $O(n^2)$ 。 B Distinctification考虑给定一段序列怎么算出答案。不难发现对于一个 $A_i$ ，我们一定会找到一个最大的 $k$ 满足 $[A_i, ...

考虑对于一个数组 $a_{1,\dots ,n}$ 怎么求出答案，其中 $0$ 为根。考虑每一条边 $i \to f_i$ 的贡献，显然是 $siz_i(n+1-siz_i)$ 。那么我们可以枚举这个点的子树的 $siz$ 然后算这种情况的概率，而算概率则直接统计有多少种加边后的方案使得取到这个 $siz$ 然后除以总方案数 $n!$ 即可。考虑方案数量的计算，如果确定后面有 $s$ 个点在子树内（不包括 $i$ ），这些点的父亲的方案分别是 $1,2,3,\dots ,s$ ，因为第一个子树内 ...

其实这个东西可以 OEIS 到，不过还是正经写一下吧。 考虑如何求出 $P(x)$ ，我们对它质因数分解成 $\prod p_i^{c_i}$ ，然后会发现这个东西可以对每个质因数分开考虑，最后使用 CRT 合并即可。考虑对于一个 $p_i^{c_i}$ ，它的阶是 $\varphi(p_i^{c_i}) = (p_i-1)p_i^{c_i-1}$ 。首先讨论 $p_i \ge 3$ ，设原根为 $\omega$ ，那么有 $\omega^{(p_i-1)p_i^{c_i-1}} = 1$ 。讨 ...

有意思的题。 这个问题是有一个普遍结论的：在 $\frac n e$ 附近之前全部不管，之后就遇到一个位置为前缀最小值则直接选。 考虑这个东西是怎么来的。我们设 $f_i$ 表示 $1 \sim i-1$ 都不管，从 $i$ 开始遇到一个位置为前缀最小值则直接选择，最终得到 $1$ 的概率。 考虑转移，分类讨论一下这个位置是否是前缀最小值。显然一个位置作为前缀最小值的概率是 $\frac 1 i$ ，而这个位置是前缀最小值时它是 $1$ 的概率是 $\frac i n$ ，那么式子就是： f_ ...

考虑如果能建立出前后缀的最小生成树，然后就只需要往里面添加开头向结尾的边的问题。 然后会发现，实际上这些边只会连接开头、结尾这 $2n$ 个点，由于断边也只会断这 $2n$ 个点中两两路径上的一些最大边，于是我们考虑维护出每个前缀和后缀的生成树上这 $n$ 个点的虚树，虚树上边权就是路径上边权的最大值。由于这样虚数点数是 $O(n)$ 的，所以甚至可以对每个前缀和后缀的虚树都存下来！ 但是怎么维护这样的虚树呢？比如我们维护了 $[1,i]$ 的虚树，考虑加入 $i+1$ 这一列的点求虚树。不难发 ...

好题。首先我们考虑一天之内能到达的情况。我们考虑对于每一对 $s,t$ 求出一个最晚的时间 $T$ ，使得在 $T$ 之前的时刻出发，都可以在当天到达 $t$ （这里要注意有可能一天之内到不了，也就是可能 $T < 0$ ）。 这个东西如何计算？首先有一种非常暴力的想法，我们每次加入一个当前连通块连出去的边，同时可能导致 $T$ 减小，然后重新跑一次最短路。考虑这样的复杂度，枚举点 $O(n)$ ，加边次数是 $O(n^2)$ ，每次跑最短路使用 dijkstra （这里显然 $O(n^2 ...