病毒扩散  题目描述 题目讲的很清楚，这里就不加赘述了。 正解 考虑病毒扩散的组合意义，把它转化成从 的方案数。 一个点它在一秒内可以进行以下三种操作。  不动  （往上走  （往右走  至于这样为啥是对的，自己感性理解一下吧，直接讲也不太好讲。 最后答案就是 。 upd : 证明 考虑暴力更新大小为 的矩阵的过程。 有 。 第一项其实就是在这一秒不动，然后第二项是在这一秒往上走，第三项是在这一秒往右边走，对应着上面说的三种操作。 后面答案为啥是那个组合数呢？ 我们要求的东西其实是：在 秒内，走 次向上的，走 次向右的，那么这个组合数就自然是没有问题滴。 代码 #include <bit...

牛妹的游戏  题目描述 给定一个无向图，问这个图中是否存在三元环，或者这个图的补图中是否存在三元环。 正解 三元环计数有一个很经典的根号分治的做法，这里不详细讲，网上博客讲得很清楚。 补图的边是 级别的，就不能三元环计数了，怎么办？ 由于边很多，随机三个点找到三元环的概率很大，直接随他大概 次就行。 时间复杂度 。（） 代码 #include <bits/stdc++.h> #define N 50005 using namespace std; int n, m; int x[N], y[N], deg[N]; int p[N], tot; vector<int> g...

子序列  题目描述 给定一个序列，问有多少子序列满足 。 正解 这种子序列里面元素不独立的题一般不好做，考虑如何将元素的值独立。 现在 和 的值独立了，发现原问题就是求一个上升子序列个数。 用树状数组单点加，区间求和可以做到 。 注意到 并不是整数，但其实只要知道相对大小就行，即还需要离散化。 代码 #include <bits/stdc++.h> #define N 105 using namespace std; const int mod = 1e9 + 7; const double eps = 1e-10; int n; int a[N]; namespace BIT {...

边的染色  题目描述 给定一个无向图，边权为 0 / 1。 给定一些边的权，然后要你去把剩下的边权给定了。 要求对于图中每一个环,边权异或和为 0。 求方案数对 998'244'353 取模。 正解 先给出一个构造解的方法：将每一个点随便定一个点权，然后令边权等于两端点权异或和。 这样一定是合法的，因为一个环内每个点恰好出现了（被异或）两次（环内每一个点的度数都为 2）。 发现这样子给定点权的方案可以唯一对应一种给定边权的合法方案。 现在考虑题目中的边有什么用 —— 限制点权。 不考虑 -1 的边，因为 -1 的边对于点权并没有限制。 那么在一个联通块内，选择了一个点，那么联通块内所有的点的选...

牛牛与序列  先口胡一下做法，明天再来补充一下吧。 主要问题其实是求单调不降的序列个数。 考虑把原序列转化成差分序列。 然后就是一个插板的事情了。  #include <bits/stdc++.h> #define N 1000005 using namespace std; const int mod = 998244353; int n, k; int fac[N + 3], ifac[N + 3]; inline int perm(int x, int y) { return 1LL * fac[x] * ifac[x - y] % mod; } inline int com...

密码系统  题目描述 给定一个长度为 的环状字符串。 将这个字符串划分成 段，每段长度为 ，这个划分的代价为字典序最大的划分子段。 求所有划分方案下，字典序最小的划分代价。 题目太难描述了自己看题吧。 正解 环状字符串按照套路先倍长，然后枚举起始位置就能枚举到所有的划分了。 现在问题就是如何快速求出一个划分的代价。 考虑后缀排序，求出每一个后缀的排名。 然后一个划分的代价其实就是区间（并不连续，类似于区间 ）的排名取 max。 这个可以用线段树或者单调队列做，时间复杂度 / 。 总复杂度 。 吐槽 这题后缀排序怎么卡二分 + 哈希啊，让我这种不会 SA 的人怎么活啊。（我的 SA 是直接蒯 L...

牛牛的数学题  题目描述 辣鸡多项式板子题不配拥有描述。 正解 先来康康三道模板题。  子集卷积 多项式乘法 快速沃尔什变换  题目中那个一坨，其实相当于分别按顺序做上面的三个东西。 这题真的很没有营养，会就会，不会怎么想都写不了。  #include <bits/stdc++.h> #define N 262144 using namespace std; const int mod = 998244353, inv2 = 499122177; int n; int rev[N], lim, hib; int A[N], B[N], C[N], D[N], popc[N]; in...

最短路变短了  题目描述 给定一个有向带权图，每次询问将一条边反向会不会使 的最短路变短。 正解 先以 1 号点为源点在正图跑最短路，第 个点的距离记为 。 再以 号点为源点在反图跑最短路，第 个点的距离记为 。 设 号边为有序三元组 。（题目给定的） 修改 号边，最短路变短当且仅当 。 为啥呢？ 如果不走 号边，那么最短路显然不会变短。 如果走 号边，那么最短路一定是 。  #include <bits/stdc++.h> #define N 200005 using namespace std; int n, m, q; int u[N], v[N], w[N]; int he...

相似的子串  题目描述 给定一个字符串，询问出现次数大于等于 的最长子串的长度（子串不相交）。 正解 二分 + 哈希。 首先答案显然满足单调性。 二分长度 后，如何判断答案可行？ 设 表示以 为开头，长度为 的子串，到 为止，在不相交的情况下，最多出现了多少次。 更新 数组的时候有个比较显的然贪心，即记录从左往右扫的时候，最右出现的与 相同的子串（且与当前子串不相交）出现位置的开头。 查找子串的时候利用哈希表查询相同的哈希值即可。 如何做到不相交？ 一个子串的 数组记录在开头，而在子串的尾巴位置插入哈希表，就可以做到不相交。 时间复杂度 。 一开始交了一发 map 的，多了个 然后没过 QnQ...

苹果树  题目描述 给定一棵大小为 的树，每一个点上有一个物品，物品的属性 。 有 次操作，操作分两类，修改和询问。  修改给定 , ，表示点 新增了一个属性为 的物品。 询问给定 , , ，询问距离节点 最近的一个 "带有属性的物品" 的节点（下面称这种节点为关键节点）。   正解 如果是随机树的话，那么有一个小 trick，在两个点的 lca 计算贡献。 每一个点 维护一个动态开点的线段树，区间 维护的是距离点 最近的关键节点。 修改每一个点的时候暴力往上跳父亲（树高为 ），然后在祖先修改线段树。 查询的时候同样是暴力往上跳父亲，在祖先查询最近的关键节点。 复杂度为 。 现在考虑树不随机怎...

环球旅行  题目描述 给定一棵大小为 的树，让你断一条边，使得树上距离最大值最小。 正解 先求出树直径的两个端点 ，，最后断的边肯定是直径上的边。 考虑枚举这条边，然后快速统计答案。 先可以预处理出直径这一条链，然后求出链上前缀的直径和后缀的直径就可以 统计答案了。 断掉直径上的边后，两边联通块的直径肯定分别是 （考虑树直径的性质，反证法可以证明）。 那么好办，对于直径上的每一个点，求出它挂出去的链的最远距离即可。 时间复杂度 。 出题人不给大样例还得自己打对拍，差评。  #include <bits/stdc++.h> #define N 1000005 #define inf ...

回到过去  题目描述 给定 给物品，第 个物品的大小为 ，如果两个物品大小相同，则这两个物品为一类。 要求选出一些物品总大小为 ，对于所有类别的物品，询问它是否必须被选至少一个。 不同类的物品，总大小不超过 ，且保证存在一种方案可以选出总大小为 的物品。 正解 暴力想法是对于每一类物品，不选它，然后跑背包看能不能凑出总大小为 的物品。 有一个特别优美的性质就是不同类的物品总大小不超过 ，这说明了最多只有  种物品。 但是暴力跑背包时间复杂度还是不对，是 的，就算用 bitset 优化还是跑不了。 但只要预处理出前缀的背包状态，和后缀的背包状态，对于一个类 ，就只需要 的时间复杂度就可以判断是否...