分析 读完题，我们发现为了满足所有节点 。通过不等式变形 。那么我们就有了 的做法，是过不了的，所以必须优化，我们现在为了去掉绝对值符号，所以考虑从左到右和从右到左分别进行一次转移。令 。那么，根据 的函数图像非常容易得到 那么满足这个式子的，我们直接通过决策单调性优化就好了，时间复杂度为 ，在 上还有一个加强版 。卡掉了分块+rmq的做法。 代码 #include<bits/stdc++.h> using namespace std; const int N = 5e5 + 10,inf = 2e9; int ans[2][N],h[N],n; int read(...

原根 这个的用处还是非常大的 在模意义下的乘法可以通过原根转换为加法。 NTT 需要原根。 定义 ，且 。则称 是 的一个原根。 是否有原根 只有 ，其中 为奇素数 ， 为正整数。 计算最小原根 这里直接使用最常见的作法。由小到大枚举 。 。那么只需要判断 就可以了，如果有一个为 ，则这个数不是 的一个原根。根据一些玄学引论， 的最小原根是 级别的，所以即使 很大，这个的时间复杂度仍然可以接受。 证明 考虑反证，令 而且 。且 。根据欧拉定理 。所以我们可以解一组二元一次方程，根据裴蜀定理 。所以 。所以必定满足至少一组 。这与上文相违背，所以得证。...

引入 现在市面上大多数解决 问题的一般是 预处理， 回答的线段树，平衡树。 预处理， 回答的 表，猫树。 预处理， 回答的分块加 表，这种神仙算法。 这里考虑使用 的 预处理， 回答的算法，这里用求区间最大举例。 Cartesian-tree 对于笛卡尔树，我们可以根据性质，对于一个节点 ，它的子树的任意权值都比 要小，因为笛卡尔树是满足 的性质的，所以节点 一定是管辖的一个连续的区间的。根据笛卡尔树的性质，那么 的最大值就是节点 的 的权值。 tarjan 关于 求 。这里是一种离线算法，总的复杂度为 不考虑并查集的常数。这个的讲解网上很...

分析 去专门学了笛卡尔树，找了一道模板题来做。由于我们建立的笛卡尔树满足小根堆性质，因此 的子树内的结点的高度都大于等于 。而我们又知道 子树内的下标是一段连续的区间。所以 。通过单调栈构建笛卡尔树，时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 110000; int lc[N],rc[N],st[N],top,n,a[N],si[N]; #define LL long long LL ans; void dfs(int x) { if(lc[x]) dfs(lc[x...

分析 主要考察最小割的性质。我们发现如果一条边是可行边，那么一定要满足以下性质。 满流，没有第二条增广路 。考虑证明，如果没有满流，那么我们完全没必要割去这条边。如果有，那么证明这个路径还可以继续增广，不满足最小割的定义。那么如果一条边是必须边。 满流，直接链接 所在集合。这里考虑最小割的定义。 那么我们只需要通过 把 求出来就行了。数组开的很奔放，不用太在意。 代码 #include<bits/stdc++.h> using namespace std; const int N = 4e5 + 100,inf = 0x3f3f3f3f; int read() { ...

分析 一眼的数学题。因为原问题并不好做，按照正难则反，我们先考虑容斥。定义 表示至少有 对情侣坐在了一起。那么 。 为容斥系数。考虑单独的 如何求解。那么我们发现这是在求一个圆排列，根据 元素构成的圆排列方式为 。所以 。 表示 个有标号的元素的圆排列方式。最后 。注意一下空间限制，对于 要预处理。时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long int read() { int x = 0,f = 0;char ch = getchar();...

分析 如果我们读完题发现我们要求的是这个 ，定义一个二元组 ，根据 定理，可以推导到 在一波无情的推式子之后，这道题就做完了。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long LL read() { LL x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();} while(isdigit(ch)) {x = x * 10 + ch - '0';c...

分析 我们对于一个节点 考虑，如果有一个点 两维都大于 ，那么这个节点肯定不可能作为结尾。因为考虑一下，如果排列先出现 ，那么这个两维都是单调不降的，所以不可能转移到 ，反之，如果先出现 ，它一定保持不住结尾，最后整个图构成了一个有向无环图，每一个节点可以等概率转移到后置节点。那么一个节点对于它后面节点贡献就为，令考虑前 个，当前节点为结尾的概率 。那么它的贡献的计算 。因为它的贡献要被后面的节点等概率转移，所以 。那么这个就是个二维偏序的问题，考虑树状数组优化。先求出 。然后由小到大枚举 就好了，最后还要乘以所有方案数。时间复杂度为 。 代码 #include&l...

分析 读完题，我们发现就是求 。因为 是一个素数，那么我们根据欧拉定理 。那么我们其实就是求 。好像到这里我们没法快速计算组合数了，可以考虑 定理，但是 并不是一个素数。那么我们先考虑唯一分解，对于 的每个素因子，发现最大的素因子才 ，最后在通过中国剩余定理合并。时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long #define int long long LL read() { LL x = 0,f = 0;char ch = getchar(); ...

分析 其实如果一条边链接了两个颜色不一样的节点，其实这个边根本没有任何意义，因为你从任意方向都不可能进入这条边，那么我们只需要用并查集维护集合数量就可以了。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();} while(isdigit(ch)) {x = x*10 + ch - '0';ch = g...

分析 因为一个节点 只有可能从 转移过来。考虑枚举余数，那么令 表示在节点 数字 是否可以表达。那么答案为 。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();} while(isdigit(ch)) {x = x*10 + ch - '0';ch = getchar();} ret...

分析 如果考虑 ，而因为可以向回走，所以状态并不好转移。这里直接考虑最短路算法。走路就是在两两个站中加双向边，而站台就是加从左向右的单向边。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10,inf = 0x3f3f3f3f; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();} while(isdigit(...