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

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

考虑一个 $dp$ ，设 $dp[R][t]$ 表示在 $t$ 时刻已经解决了 $1 \sim R$ 的所有患者。考虑转移就是枚举下一个治疗计划用哪一个。设下一个治疗计划为 $(l,r,c)$ 那么分为两类： $c > t$ ，那么在下一次使用治疗计划的时间在现在之后，由于中间不能有剩余的患者，有 $l \le R-(c-t)$ ，也就是 $c > t,l + c \le R+t$ 。 $c < t$ ，也就是说之前进行了一次治疗计划用来覆盖 $R$ 后的一段，那么中间没有剩 ...

一道很有意思的题，我也不知道这个题解是否写清楚了。。 设 A 是 Gennady ， B 是 Georgiy 。 首先考虑如何找出所有会使游戏无限进行下去的点。这种点分为两种，一种是从这个点，A 先手出发，就会导致最终平局，还有一种是 B 先手出发却会导致不得不平局。 首先考虑所有出度为 $0$ 的点，显然不管谁从这个点先手，游戏都会结束。 由于 A 的决策是尽量平局，所以一个点 A 出发无法平局当且仅当它的所有后继点都是 B 出发会导致不平局的情况。 由于 B 的决策是尽量不平局，所以一个点 ...

从一般的求字典序最小的拓扑排序入手。考虑第一次加入无入度点后，得到了一个小根堆 $mn$ 。我们的目标是让这一次拿的是这个小根堆里面尽量大的数。先假装 $k$ 足够，于是我们把这里面除了最后一个数之外的所有数全部丢出小根堆并且维护到一个大根堆里面。然后对于最后一个数，如果它比大根堆的最大值还大，显然没有必要把它丢出去，直接用就是最优的。否则，肯定是把它也丢出去，然后拿大根堆里面的最大的出来，从拓扑序上上一次的点向这个点连边，这样一定能钦定在字典序最小的情况下，这个点的位置就在这里。 也就是说，当 ...

为了做这个题学了一下支配树大概是个什么玩意。一般图支配树被鸽了，只写一下 DAG 上支配树的做法。 考虑一个单源有向图，上的一个点 $u$ 如果存在一个点 $v$ 满足删除 $v$ 后 $u$ 无法从源点到达，那么我们称 $v$ 支配点 $u$ 。 显然，同一个点的支配点很多，设这些点是 $v_1,v_2, \dots ,v_k$ ，同时显然源点也是一个支配点。 如果 $a$ 支配 $b$ ，$b$ 支配 $c$ ，那么有 $a$ 支配 $c$ 。证明显然。 如果 $a$ 支配 $c$ ，$b ...

也是道不错的题，大概是第一次做到按点权建 Kruskal 重构树。 捐赠的过程是一个经典的问题，一般的做法是倒着考虑后贪心。倒着考虑这个问题，于是变成了选择一个初始点，在任意点的时候身上的钱的数量必须不小于 $\max(A_i - B_i , 0)$ ，并且到达一个点后就可以选择获得 $B_i$ 块钱，你需要最小化最终的钱数。 为了方便，我们设 $C_i = \max(A_i - B_i , 0)$ 。如果是个完全图就可以直接按照 $C_i$ 从小到大贪心拿。但是事实上，由于具有图的限制，想要拿 ...

需要注意的是，这个题当把一个颜色合并进选择的颜色后，会导致一些其他的颜色原本无法影响最开始选择的颜色，但是合并后会影响了。也就是说影响关系是具有传递性的。 因此考虑如果设定一个颜色 $i$ 为首都需要将另一个颜色 $j$ 合并进 $i$ ，那么加边 $j \to i$ 。这样加边后，显然只需要一次缩点就能求出答案。具体来说，最后选择的一定是入度为 $0$ 的点，并且需要合并的次数就是这个点的大小 $-1$ 。 考虑怎么进行加边。我们考虑以 $i$ 作为首都，那么显然将 $i$ 颜色建立虚树后所有 ...

神仙题。不愧是 3500 。 我们考虑对于每个数，它必然有一个脱离限制的位。也就是说，每个位置实际上放的值，必然是和 $L$ 或者 $R$ 存在一段 $\text{LCP}$ ，然后下一位脱离限制，然后后面的随意填。 于是我们考虑一个贪心，如果我们知道了 $1 \sim n$ 的所有数中脱离限制位最低的是谁，那么这个脱离限制位之下的所有位对于所有数都是可以随便放的，所以我们一定全放 $0$ 或者全放 $1$ 最优。 我们可以把这个问题推广到任何一个区间上。对于一段区间 $l,r$ ，我们可以枚举 ...

CF1204E Natasha, Sasha and the Prefix Sums首先，看到这个 $\max$ 可以想到转化成求和最大值大于等于 $i$ 的方案个数。 按照这种 prefix sum 的一般想法，会发现这个东西就是画成折线后和 $y=i$ 的交点。然后枚举 $i$ 分情况讨论，由于结束点显然在 $(n+m,n-m)$ 那么： 如果 $n-m \ge i$ ，显然必然有交点。方案数为 $\binom {n+m} n$ 。 否则，我们考虑把 $(0,0)$ 翻折到 $(0,2i) ...

每天只挑最简单的做就是我了 称有人的点为关键点。 首先观察样例会发现，如果关键点的个数为奇数，答案肯定是 $1$ 。我们设任意一个开会地点为 $u$ ，那么显然有所有儿子子树内的关键点个数不超过一半，而又是奇数，往任何一个方向走肯定都无法使得答案保持不变，而且一定是变得不优。同时如果你一直往某个方向走，原本子树大小不超过一半之后也一定不超过，所以一定会越来越不优。 类似的思路，考虑偶数的时候，如果存在多解，肯定是找到了一个点，使得所有点被平均分配到两个子树里面，这样就可以把根向这两个子树移动，如 ...

考虑什么样的排列可以通过 $k$ 次操作达到。不难发现当且仅当排列中存在一个区间，满足区间单增且区间长度 $\ge n - k$ 。由于存在会比较难以统计，可以考虑求出所有极长连续段长度 $\le n - k - 1$ 的排列数量，然后用 $n!$ 减去即可。 考虑枚举 $t$ ，计算所有极长上升段都 $\le t$ 的方案数。考虑一个暴力，先暴力对整个序列分段，令这些段就是极长上升段，然后不难发现限制是 段内 $<$ 和 段间 $>$ 。这个东西非常难以统计，所以考虑容斥掉 $&g ...