4.25 写题
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})$ ,不难发 ...
阅读更多
AUOJ415 s2mple 的字符串
一个我没写过的套路。 这个题目其实就是问你给你一个串,可以往前添加一些字符,往后添加一些字符,有多少种添加方式使得最终串不同。 我们先考虑向前添加字符,不难发现一个字符串向前添加字符可以得到的就是 parent 树子树内的本质不同的所有字符串。设这个串长为 $|S|$ ,子树内的本质不同串的个数为 $a$ ,当前点上最短串长为 $b$ ,那么添加方案数就是 $a+b-|S|$ 。 我们考虑往后添加字符的情况,往后添加一个字符就是在 SAM 的 DAG 往后走一步。所以如果我们设往后添加了 $k$ ...
阅读更多
CF1451F Nullify The Matrix
我们按照与对角线平行的线上的数来考虑。如果只考虑在一条这样的对角线上进行操作,那么就变成了一个普通的 Nim 游戏。而如果有很多对角线,不难发现在进行一次操作的时候,这个人可以把后面的所有对角线的状态改变。 于是我们考虑找出第一个异或和不为 $0$ 的对角线,这个对角线单看是先手必胜的。考虑先手对这个对角线进行一次操作把它的异或值变为 $0$ 。要么此时已经没有数了,先手胜利。要么后手会有一些选项:选择这条对角线或之前的对角线,这样的话必然会导致一条对角线的异或和变成非 $0$ ,先手可以继续操 ...
阅读更多
积和式模 4
首先,模 $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$ 由于只有最多一个位置为 ...
阅读更多
4.17 题
A Winding polygonal line神仙构造。 考虑拿凸包上一个点 $A$ ,然后每次找一个点 $B$ ,如果是 L ,则使得剩下的所有点都在 $AB$ 的左侧,然后连过去即可,否则就使得所有点都在 $AB$ 右侧。不难发现这样每一轮都一定能找到剩余点继续,且由于所有点都在一侧,显然不可能出现线段相交。 复杂度 $O(n^2)$ 。 B Distinctification考虑给定一段序列怎么算出答案。不难发现对于一个 $A_i$ ,我们一定会找到一个最大的 $k$ 满足 $[A_i, ...
阅读更多
AUOJ422 生成无向图
考虑对于一个数组 $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$ ,因为第一个子树内 ...
阅读更多
LOJ3403 「2020-2021 集训队作业」function
其实这个东西可以 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$ 。讨 ...
阅读更多
AUOJ471 咕
有意思的题。 这个问题是有一个普遍结论的:在 $\frac n e$ 附近之前全部不管,之后就遇到一个位置为前缀最小值则直接选。 考虑这个东西是怎么来的。我们设 $f_i$ 表示 $1 \sim i-1$ 都不管,从 $i$ 开始遇到一个位置为前缀最小值则直接选择,最终得到 $1$ 的概率。 考虑转移,分类讨论一下这个位置是否是前缀最小值。显然一个位置作为前缀最小值的概率是 $\frac 1 i$ ,而这个位置是前缀最小值时它是 $1$ 的概率是 $\frac i n$ ,那么式子就是: f_ ...
阅读更多
SDOI2019 世界地图
考虑如果能建立出前后缀的最小生成树,然后就只需要往里面添加开头向结尾的边的问题。 然后会发现,实际上这些边只会连接开头、结尾这 $2n$ 个点,由于断边也只会断这 $2n$ 个点中两两路径上的一些最大边,于是我们考虑维护出每个前缀和后缀的生成树上这 $n$ 个点的虚树,虚树上边权就是路径上边权的最大值。由于这样虚数点数是 $O(n)$ 的,所以甚至可以对每个前缀和后缀的虚树都存下来! 但是怎么维护这样的虚树呢?比如我们维护了 $[1,i]$ 的虚树,考虑加入 $i+1$ 这一列的点求虚树。不难发 ...
阅读更多
JOISC2021 D2T1 Escape Route
好题。首先我们考虑一天之内能到达的情况。我们考虑对于每一对 $s,t$ 求出一个最晚的时间 $T$ ,使得在 $T$ 之前的时刻出发,都可以在当天到达 $t$ (这里要注意有可能一天之内到不了,也就是可能 $T < 0$ )。 这个东西如何计算?首先有一种非常暴力的想法,我们每次加入一个当前连通块连出去的边,同时可能导致 $T$ 减小,然后重新跑一次最短路。考虑这样的复杂度,枚举点 $O(n)$ ,加边次数是 $O(n^2)$ ,每次跑最短路使用 dijkstra (这里显然 $O(n^2 ...
阅读更多