Problem - 1641C - Codeforces 一道不是很会的数据结构题。 这里很明显的就是变成 $0$ 的区间是不需要考虑的，我们只需要考虑变成 $1$ 的区间。 这里会有一个问题，如果新加入了一个变成 $0$ 的区间，那么我们之前变成 $1$ 的区间就是有可能产生贡献的，所以我们要不离线要么就是通过数据结构进行存储。 笔者发现离线一下子不是很好想，所以考虑使用数据结构进行维护，根据上述的条件发现我们不能时刻保证手上都有答案，所以需要再进行询问的时候来计算答案。 不妨考虑进行询问 $x$，显然如果 $x$ 已经被明确说明过没有病直接回答 NO 即可，剩下的就是可能有病的情况，考虑什么样的一个区间才可能能确认 $x$ 是有病的，显然就是一个区间只有 $x$ 是不确定的，我们考虑找到这个区间的范围，就是最左边连续的确定没病的位置 $L$ 和最右边的 $R$，我们考虑对于 $1$ 区间的左端点在 $[L, x]$ 之间如果右端点 $\le R$ 那么肯定是合法的。 显然右端点肯定不会 $< x$ 不然区间之间就会产生矛盾。 我们通过维护区间最小的右端点即可，使用线段 ...

Problem - 1641D - Codeforces 事实上有很多种做法，比如随机化等等。 我们考虑如何判断两个集合是不同的从而推广到一个集合和多个集合的情况。 显然暴力判断复杂度是不能接受的，我们考虑通过枚举集合进行判断。 我们考虑一个式子 $\sum_{S_1 \subset A} \sum_{S_2 \subset B} [S_1 == S_2] $ 表示总共有多少个集合是相同的，也就是不妨设 $A \cap B = S$，那么本质上就是 $\sum_{i \ge 0} \binom{|S|} {i} $，我们灵光一闪发现 $\sum_{i \ge 0} \binom{n} {i} (-1) ^ i = [n == 0] $，我们可以通过这种方法来快速判断集合是否有交。 那么很简单，对于判断 $A$ 和若干个集合是否有交，我们可以考虑对于若干个集合建立一个扩展 $\tt Trie$ 树，之后直接暴力枚举 $A$ 就可以了，复杂度是 $2^m$。 之后我们考虑进行贪心，我们不妨将每个数组按照 $w$ 的大小进行排序，之 ...

一些定理和定义就不说了史上最通俗的后缀自动机详解 - KesdiaelKen 的博客 - 洛谷博客这里都有。 我们具体说一下后缀自动机初学者难理解的地方。 什么是后缀自动机：本质就是一个 $\tt Trie$ 树和 $\tt parent$ 树重叠的东西。 三种分类讨论怎么理解：首先我们清楚我们加入的是一个点（字符 c ）而不是一个串，我们加入了一个点，我们通过 $\tt Trie$ 树的转移不妨设其为 $\tt trans[u][c]$ 表示在 $u$ 之后加入一个字符 c 得到的位置。 显然从空节点开始走到达某个节点 $u$ 构成一个字符串，同时也是原串的子串。 为了方便说明我们不妨设没有加入字符 c 的串是原串，加入之后为当前串。 第一种情况 我们通过跳后缀链接，尝试找到是否存在原串后缀加上节点 c 得到的节点。如果不存在那么我们新加入的 c 显然是不存在的，我们直接链接根节点即可。 为什么说是不存在的，考虑直接从根节点都走一步都走不到 c。 第二种情况 我们幸运地找到了当前串的后缀，不妨设节点为 $u$，而且更加幸运的是 $u$ 表示集合与 $\tt trans[u ...

Problem - 1634E - Codeforces 注意都是偶数的性质，我们尝试考虑建立欧拉回路。 因为欧拉回路上每个节点的入度等于出度，我们直接将限制建立成点即可。 也就是对于每个数组建一个点，每种颜色建立一个点，如果数组 $i$ 中有颜色 $j$ 那么我们就建立无向边 $(i, j)$，我们将这个位置的标号当做边权，不妨钦定 $i \to j$ 的边我们将其设为 L，否则就是 R。 我们可以发现对于同一行连出去的边肯定都是在当前数组内的，所以直接开桶统计答案即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114#include <bits/stdc++.h ...

Problem - 1633E - Codeforces 首先发现询问次数是很多的，但是点数和边数是很少的。 所以我们总共有两个方向可以走一个是优化生成树，但是可以发现不管是 $\tt P, K, B$ 这些算法都是不行的，我们只能考虑另一个方法减少求生成树的次数。 比较浅层来说可以发现我们可以对于边进行排序，那么如果两个询问 $x_1, x_2$ 其在两条边 $w_1, w_2$ 之间，我们设边的中点为 $\tt mid = \dfrac{w_1 + w_2}{2}$ 那么如果其在中点的同一边那么就不需要再进行操作了。 我们可以通过这个将所有的边都进行如上操作，之后离线询问即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210 ...

Problem - 1644F - Codeforces 发现第一个操作不是很好考虑，我们优先从第二个操作入手。 如果一个数组 $a_1$ 可以通过操作 $2$ 变成数组 $a_2$ 当且仅当 $a_1$ 中每种颜色的下标集合恰好和 $a_2$ 中一种颜色的集合对应。 也就是意味着我们需要的 $a_1$ 其实不一定要考虑颜色，只需要计算出不同的集合的集合的数量即可。 也就是在 $n$ 中选出 $i$ 个集合，本质就是第二类斯特林数。 之后我们再考虑操作 $1$，显然我们原来多算了答案，对于 $F(a_1, j), j > 1$ 我们发现每个数组都是可能变成一个新的数组，显然存在 $F(a_1, j) = F(a_1, 2j)$ 的情况，就是说明需要容斥来解决。 时间复杂度是 $\sum_{i = 2} ^ n O(\frac{n}{i} \log \frac{n}{i})$ 我们知道调和级数的复杂度是 $O(n \log n)$ 的，那么后面加一个 $\log$ 就是 $O(n \log ^ 2 n)$，可以通过此题。 对于容斥系数的处理，我们可以枚举倍数计 ...

Problem - 1632E2 - Codeforces 首先有一个很直观的解法，发现对于连边肯定是贪心去连最长链到根节点的一条边，之后通过两遍 $\tt dfs$ 来找到答案，复杂度 $O(n)$。 但是上述的解法有很明显的问题： 如何选择最优的最长链？ 为什么不可以连接到两个点的中间？ 我们着重按照这个问题来思考解法。 既然已经知道了肯定是连接根节点的边，我们考虑对于两个深度都大于当前答案 $\tt Ans$ 的点，我们如何才能找到最优的解，设其距离为 $\tt dis$。我们显然可以让两个点的 $d$ 变成 $\tt \lceil\frac{d}{2}\rceil + L$。 就是在路径的中间的某个点连接根节点。 对于所有的这样的点我们都需要考虑一遍吗？ 其实我们只要考虑两棵子树中深度最大的点构成的距离即可。 事实上到这里这个题目就做完了，还有一些细节需要完善，已经明白的大佬可以直接去看代码。 对于这样的两个点，显然深度小的点如果不需要考虑那么对于深度大的点我们可以直接进行连边，所以这个点对生效当且仅当 $\tt Ans$ 小于深度较小的点。 我们显然不需要考虑 ...

多项式计数杂谈 - command_block 的博客 学习总结 二项式 $\color{red}(1)$ 拆开组合数 $$\binom{n}{m} = \frac{n!} {m!(n - m)!}$$ 组合意义就是总共有 $n$ 个物品，我们选择 $m$ 个出来的方案数。 根据组合意义，我们需要有 $0 \le m \le n$ 才能保证成立。 一些推论： 对称性 $\binom{n} {m} = \binom{n} {n - m}$ 吸收恒等式 $\binom{n} {m} = \frac{n} {m}\binom{n - 1} {m - 1}$ $\color{red}(2)$ 经典二项式定理 $$(x + y)^k = \sum_{i = 0} ^ k \binom{k}{i}x^iy^{k - i}$$ 注意 $1$ 的幂可能隐藏在求和中。 $\color{red}(3)$ 递推公式 $$\binom{n}{m}= \binom{n - 1}{m} + \binom{n - 1}{m - 1 } ...