参考：http://www.algonotes.com/en/counting-matchings/ 和四川省选 D 官方题解。 下午研究 FKT Algorithm 的时候发现了这篇博客，弄明白后觉得非常巧妙，而且实现极为容易！ 仍然有一些只会感性理解不会严格证明的结论… 题目描述给定一个 $n \times m$ 的棋盘，求有多少种在棋盘上放置 $1 \times 2$ 的多米诺骨牌使棋盘密铺的方法。同时，对于每个位置 $(i,j)$ ，分别给出在 $(i,j)\to (i,j+1)$ 和 ...

A [CTSC2010]星际旅行我们考虑每次旅行收益一样，提示我们这题很可能可以贪心。然后考虑每个点有 $H_i \ge deg_i$ ，可以发现这正好是从 $1$ 出发遍历所有点然后回到 $1$ 的代价，于是我们先考虑终点在 $1$ ，直接把这个代价减掉，得到新的 $H_i$ 。此时能够增加答案的方法就是选择相邻的两个点把他们的 $H$ 同时减少 $1$ ，然后路径上就是进行一次左右横跳，会让答案增加 $2$ 。 这个过程显然是可以贪心做的（因为一个点）把 $H$ 留着匹配上面的收益和往下匹 ...

A 大佬的难题首先这题本身是一个裸的三维数点，直接做复杂度 $O(n\log^2 n)$ ，虽然各种卡常导致看起来随机数据是可以进 2.5 的，但是终测性能太差还是卡掉了！ 我们考虑一个容斥。我们考虑对三个序列两两求一次二维偏序问题，这个问题复杂度显然是 $O(n\log n)$ 的。然后考虑对于一对 $i,j$ ，设满足偏序关系的维度数是 $k$ 。如果 $k = 0,k = 3$ ，它的贡献显然都是 $3$ ，也就是三次求二维偏序都把它算进去了。如果 $k = 1,k = 2$ ，那么它的贡 ...

A 哈密顿回路被阴间到了，给了一个 $G_{i,j} < G_{i,k} + G_{k,j}$ 的没用条件看了很久发现确实没用，最后暴搜一下就跑过去了。。 我们折半搜索一下，具体来说，对于 $n = 14$ ，我们搜出 $1$ 出发的所有点的个数为 $7$ 的路径，再搜出所有 $1$ 出发点的个数为 $8$ 的路径，然后拼起来即可。复杂度大概是一个和 $\binom{13}{6}$ 有关的东西。 写完后试了试，发现跑的非常慢。这里写一下我的优化方法： 由于最后只需要合并一次，不需要开 s ...

A 圆圈游戏一道优秀的扫描线题。 我们考虑没有相交和包含，提示我们可以通过包含的关系建立出一棵树，一个点的儿子就是它极大的包含的圆。 如果能够建立出这个树，那么我们可以在树上做一个非常 trival 的 $dp$ 解决问题。转移就是枚举选不选这个点。 我们考虑怎么建立这个树。考虑从左往右进行扫描，到达一个圆的左端点的时候就加入这个圆，到达右端点的时候删掉他。我们考虑在删掉一个圆的时候找出它的父亲。 如果这个圆右端点向上引一条切线，考虑讨论一下这个切线碰到的第一段弧。如果这段弧是一个上圆弧，显然我 ...

A Training相当于是要求保留的非树边和尽量大。 我们考虑所有边 $(u,v)$ ，如果距离为奇数，显然这条边必删。 如果距离为偶数，那么加入后会存在一个奇环。但是如果有两个相交的奇环，那么它们拼起来的大环的大小就是两个环长度和减去共有的部分乘二，这是个偶环。 所以我们相当于需要加入若干个点对，使得两两路径之间无交。 事实上这题还在 CERC 中出现过一个无权值的版本，那个问题由于路径权值是 $1$ ，可以证明局部最优等价于全局最优，因此 $dp$ 更加容易，但在这里行不通。 由于每个点度 ...

6.11 模拟赛A Game我们考虑所有人的初始情况是一样的，所以可以逐一确定每个人的做任务情况。 所以有了一个朴素的想法，我们设 $dp[i][j]$ 表示前 $i$ 个人，一共已经做了 $j$ 个任务，这种情况下最小的天数是多少。不难发现，如果我们可以算出 $f(k-j,t)$ 表示一共 $k-j$ 的体力值，一共用 $t$ 天最多做多少任务的话，就可以直接 $O(nm^2)$ 解决问题。 这个东西看起来需要一个 $O(km^2)$ 的转移，但是事实上我们可以算出 $pd[i][j]$ 表示 ...

A 树考虑先化一下第一个式子，那么就是 \sum_{u\in A} d_u + \binom{|A|}{2} - \sum_{u \in A}\sum_{v \in A} [\text{u 是 v 祖先} ,w_u \le w_v] + \sum_{u\in B} \sum_{v \in B} [\text{u 是 v 祖先},w_u< w_v]然后我们不考虑 $\binom{|A|}{2}$ 。 可以猜测这个式子有特殊含义，所以把第一部分也加进这里面来统计，具体来说，我们把这个 $\sum_ ...

Topcoder 12505 CharacterBoard我们考虑如果能够枚举长度，那么每个字符对应回原串的位置就是固定的了，这样我们就可以直接 $26$ 的剩下字符个数次方得到答案。 但是事实上字符串的长度可能到达 $10^9$ ，这么考虑肯定是不行的。但是仔细想一想会发现，对于多数长度，你的 $n \times m \le 100$ 个字符根本不会有冲突。而有冲突的长度，必然是某两个字符之间差距的约数。因此我们直接枚举每两个字符之间的差距，然后枚举这个差距的约数，然后单独计算这些长度即可。剩 ...

A 宝石开场看错题 1.5h ，一直以为不能拿连续 $k$ 个宝石，然后发现 15pts 都不会，直接导致 T3 暴力都没打。。 我们考虑找出第一个位置，使得这个位置的颜色在之前出现过了，那么如果想继续往后选择，就必须把这个位置丢掉。我们一直重复找这种位置的过程，知道找到了第 $k+1$ 个，此时我们就只会在前面的东西种选择 $k$ 个扔掉。具体来说，对于每个出现了大于等于 $2$ 次的颜色我们只会保留最大的。 由于 $k$ 很小，我们可以考虑暴力做上面那个过程。每次之需要找到后面第一个重复出现 ...

懒得卡空间了！ 我们考虑对于一段区间来说，在全局加 $x$ 后，长度为 $l$ 的段的最优答案是啥。不难发现是 $lx + b$ ，其中 $b$ 为长度为 $l$ 段的和的最大值。因此我们可以对每个 $l = 1\sim n$ ，求出一条直线，然后对这个直线求一个凸包就可以做询问在全局加 $x$ 的情况下的和了。 然后考虑区间询问怎么办。首先我们可以把区间询问拆成 $O(\log n)$ 个线段树节点。然后对每个节点，我们维护出最大的后缀和，最大的前缀和，最大的区间本身子段，以及区间的和。之需要 ...

A 科学怪人可以发现，只需要求出 $(\frac{n}{\gcd(n,b)},0) , (0,\frac{n}{\gcd(n,a)}),(a,b)$ 的所有线性组合即可。 直接 bfs ，由于最终只有 $O(n)$ 对，答案是 $O(n)$ 的。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676 ...

神仙场。 A Number原题链接 对每个数码分开考虑。对于一个数码来说，我们其实需要求的是一个最小的数 $i$ 使得 \sum_{j \le i} (d - S(j,d)) < 0最后对每个数码的答案取最小值即可。 我们考虑这个东西怎么求。这个东西本身不太具有二分性，但是我们考虑对 $1 \sim 10^i - 1$ 求出这个前缀中的最小的前缀和以及整个的前缀和即可。然后我们就可以从高位到低位填数，从 $0$ 到 $9$ 枚举这位的数码，然后看看如果填入这个数后低位的最小前缀和会不会导致整 ...

三道 Petrozavodsk 和 Open Cup Different Summands Counng链接 反套路题。介绍一下 $O(m^3\log n)$ 的卡常做法和 $O(m^3)$ 的标算。 我们考虑对于一个数，算出它恰好没有出现过的方案数，然后用总方案减去这个就是出现过的方案数量。前面这个可以方便地容斥成钦定，而如果是钦定且这题是有序拆分就可以用插板来安排剩下的数。 \sum_{a=1}^n\left(\binom{n-1}{m-1} - \sum_{k = 0}^{\min(m ...

A 求出 $n$ 个数都是不到 $m$ 质数，且 Nim 游戏后手必胜的方案数。 $n \le 10^9,m\le 10^6$ 给定模数。 考虑到质数没啥好的性质，看起来也只能够去算这个异或卷积 $n$ 次方。 但是直接写完发现这东西巨慢无比。考虑怎么优化常数。 可以发现最后只需要求 $A[0]$ ，这个数在异或卷积式子可以看出为所有数的和，而 $\text{IFWT}$ 在异或卷积其实就是做一次 $\text{FWT}$ 然后每个数除以 $len$ 。因此我们最后没必要做一次 $\text{ ...

D1T1 D2T1 非常签到，就不写了。 不会真的有人写 D1T3 吧，不会吧不会吧 D1T2首先考虑部分分，部分分就是直接求 $\max[l,l+c]$ 为初始值走 $[l+c,r+c]$ 的单调栈的长度。 我们考虑设数组 $b_i$ 表示在经历若干操作后， $A_i$ 的值变成了原序列中 $[i,b_i]$ 的最大值。 考虑 $b_i$ 的转移，不难发现就是一次区间平移然后往最后插入一个 $b_r$ 。 但是即使维护了 $b_i$ 仍然不好方便地做这个东西。然后就有一个非常神仙的转化：设 $ ...

T1 NEERC2016 Cactus Construction考虑一棵树怎么做。容易想到，我们保证递归完一棵子树得时候根为 $2$ ，其他内容为 $3$ ，然后当前点 $u$ 设 $1$ ，于是每次就连 $1 \to 2$ 然后把 $2$ 整成 $3$ ，再做下一棵子树即可。这样只需要三种颜色。 考虑仙人掌咋办。还是类似地，我们尝试做完一个环的时候把最上面设置成 $2$ ，这里为了方便，可以类似圆方树把一条边也看成长度为 $2$ 的环。然后考虑类似建立圆方树的过程。如果一个儿子 $v$ 自己为 ...

终于做了一些比 入门篇 难一些的题。 A AUOJ1600 礼物其实是道板子+式子题。大概是 Burnside 引理的第一种题型（强行拼上去）。 我们考虑设 $f(a,b)$ 为 $a$ 个点形成环，从中选择 $b$ 个位置选中，且选中位置没有连续 $k$ 个的方案数量。 由于是循环同构，我们枚举置换再算环的个数，然后就可以得到和入门篇基本一样的式子，然后最后就是： \sum_{i | n,i | m} f(\frac n i ,\frac m i) \varphi(i)考虑怎么快速计算 $ ...

B Parades这题有一个关键的性质：可以发现一定有一种全局最优解满足每个点都是局部最优解。具体来说，由于每个点向上只有一条边，所以即使你在这个点子树的时候放弃选择一条路径，也只能最多获得 $1$ 的贡献，还不如直接选择子树之内。（感觉这种性质在权值全 $1$ 的时候都可以尝试一下有没有） 于是我们设 $dp[u]$ 表示 $u$ 子树最多可以选多少个路径，再对每个子树维护出一个集合，这个集合中的点满足存在一个选择最多路径的方案，使得这个点没有被覆盖。 考虑转移，由于 $n \le 10^3$ ...

A (False) faces题解在 这里 。 B Pachinko我们考虑设出 $s_{i,j}$ 表示经过 $s_{i,j}$ 的期望次数。那么可以对每个格子列出一个方程。由于每个 T 位置不会往外走，也就是说走到这个点就结束了，所以期望次数可以直接看成一个概率，最后除以会结束的总概率即可。但是直接进行高斯消元是 $O(n^3m^3)$ 的，无法接受。 然后会发现这个矩阵非常有性质。由于这个矩阵是 $n \times m,10^4 \times 20$ 的，而一个位置的方程仅在 $[i-m, ...

A Yet Another LCP Problem考虑反过来看串，如果建立前缀树，会发现这个 LCP 长度的问题就可以看成对于所有一类集合的点都到根全部 +1 ，对所有二类集合点求和。但是由于一般来说前缀树显然是建不出来的只能建出 parent 树，而如果建出 parent 树后，相当于这个点父亲到根的所有串全部 +1 ，然后需要特殊处理当前点。因此树剖显得挺难受，于是考虑建立虚树后 dfs 两遍做即可。细节可以参考代码。 复杂度 $O(n\log n)$ 对每个点上串的长度需要排序，以及建虚树 ...

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$ 这一列的点求虚树。不难发 ...