T1 简单题(simple)
题目大意：给定联通无向图，求满足以下条件的边数量：
- 每条边最多在一个简单环内（也就是环，当时愣了很久，于是就没打出来）
- 对于任意编号为 \(i，j(i < j)\) 的两点，存在一条它们之间的简单路径上面有 \(j-i+1\) 个点
首先我们可以发现，条件2很好求，就是肯定有一条从1到n的链。长这样：
为什么，因为根据条件2，任意编号为 \(i，i + 1\) 的两点，存在一条它们之间的简单路径上面有 \(2\) 个点。那么 \(i，i + 1\) 间肯定有一条边直接相连，满足了这条性质，其它的 \(i,j\) 就必定满足。
因为如果 \(i,j\) 满足了这条性质，那么 \(i,j+1\) 必定满足，根据数学归纳法，其它的必定满足。
如果这道题要求求最少边的话，我们已经做完了。
可是题目要求求最多的边，那么……
就加嘛！
我们就直接加，这里很容易可以得到一个DP：
其中 \(j\) 是与 \(i\) 直接相连的边，且 \(i_{右端点} > j_{右端点}\) 。
为什么它可以保证条件1呢？因为我们看按右端点排序后是什么样的：
当我们在 \(i = 7,j=4\) 的时候，因为 4 之前的右端点绝对小于 4，所以在 $ [4, 7]$ 这段区间内不可能出现，不会与 \([4,7]\) 交叉。
所以我们枚举 \(i,j\) 即可？非也，这么做复杂度为 \(n^2\) ，因为 f 数组必定是递增的，所以说取右边的一定比取左边的优。那么我们只需要在输入时预处理一个点距离它最近在它左边的那一个点 \(j\) 。
总结就是想复杂了，同时图论看少了（竟然不知道简单环QWQ）
T2 困难的图论
比赛时看了又看，看了又看，总结出：
这不就是割点嘛！
我们定义一个”美丽的区间“为这样（我不知道怎么描述）：
然后我们发现，对于美丽的区间C这种不是简单环的区间，最终一定是每条边可以在多个环中。
对于美丽的区间A、B这种是简单环的区间，最终一定是每条边都只在一个环中。
对于中间这种割点，它们组成的边是不属于任意一个简单环的，所以最终一定是每条边不属于任意一个简单环。
那么就好办了，用某一个神奇的算法求出这些“美丽的区间”，然后判是不是简单环即可。
Q：可是，怎么求“美丽的区间”呢？
A：当然是割点啦！
Q：割点怎么求？
A：当然是Tarjan啦（记得讲过）
Q：我忘了。
好了，然后就打了个暴力拿了 30pts。
故事讲完了，比赛时想到的神奇算法叫：点双连通分量。
这个因为篇幅有限，不讲这些算法了。
然后怎么判简单环，很简单，我们计算出一个“美丽的区间”的点数和边数，如果它们相等说明这是简单环，边数大于点数说明这不是简单环。边数小于点数说明这是一条链。
然后就是困扰了我很久的问题：怎么求边数。
点数很容易，因为我们在记录 栈 的时候就是存的点嘛，这样我们才能知道哪些是割点或者割边。边数的算法则是我从来没遇到的。
其实这是一个特例，我以前学的 Tarjan 算法都是记录点的，那么我们在记录 栈 的时候存边不久行了嘛，因为记录边可以带上左右端点，然后拿个 vis 判重不就行了？
然后就是（这题细节真多）vis的重置，刚开始用 memset 重置是会 T 的，但是我改变了一种方式，就是不重置，添加 id ，memset(vis, 0, sizeof(vis)) 就是 id ++ ，vis = true 就是 vis = id ，vis == true 就是 vis == id。
就没有然后了。
T3 随机关卡（game）
比赛时完全不会。
结束时看到了这个：
该整数在模题目指定模数意义下可以写成 \(P × Q^{−1}\) 的形式。
emm……还是不会。
结束时才发现这么简单！！！
我们知道，在某一个游戏赢一场的概率是：
选择到某一个游戏的概率是：
那么选择到某一个游戏并且赢一场的概率是：
那么赢一场的概率是：
同理，那么输一场的概率是：
继续。我们知道，在 \(n\) 次游戏里选择 \(m\)次的情况数有：
在 \(n\) 次游戏里选择 \(m\) 次赢且这些次游戏都赢了的概率有：
那么在 \(n\) 次游戏里选择 \(m\) 次赢且这些次游戏都赢了且其他次游戏都输了的概率有：
也就是说，在 \(n\) 次游戏里只赢 \(m\) 次的概率为：
因为一次理智相当于一次游戏。那么很快我们就可以得到一个数列 \(a_i\)，表示在 \(A\) 次游戏中只赢了 \(i\) 次游戏的概率，即只有 \(i\) 个理智发挥作用的概率。
可是这么求是会超时的，让我们递推吧！
首先，因为：
所以：
这就是组合的递推式，然后剩下两个就很好搞了：
（PS：上面说的 -1 次方都是逆元）
总的来说就是：
逆元使用线性求逆元。
具体百度优先搜索。
0初始值是 \((P_{lose})^A\) ，请感性理解，或者继续看下去
然后呢？又挂了。
下载数据点发现是这样的：
10 9 8
1 1 1 1 1 1 1 1 1 1
为什么会错呢，主要是因为一个数学和编程的差别，在这里， \(P_{lose}\) 是0，当 \(i = A \text{ or } B\) 时，会出现 \(0^0\)。（不是递推式，是原式 \(a_i = C^i_A\cdot(P_{win})^i\cdot(P_{lose})^{A-i}\)）
在数学上，\(0^0\) 是不存在的，但是我现在有两种解释：
- 因为当 \(i = A \text{ or } B\) ，我们是不会考虑 \((P_{lose})^{A-i}\) 的，因为 \(i = A \text{ or } B\) 意味着没有失败，这时我们只考虑成功，为了使它不会变成0，我们定义 \(0^0=1\) 。
- 在概率论中，空事件是指不会发生的事件，概率为0。在这种情况下，0的0次方定义为1，以便保持一些概率公式的一致性和简洁性。
所以这就可以结社为什么会错。我们就要特判几个特殊的 \(i\) 。
-
\(i = 0\)，这时 \((P_{win})^i\) 就可能会出现 \(0^0\) ，我们就可以使用以下公式计算
\[a_0\text{ or } b_0=C^0_A\cdot1\cdot(P_{lose})^{A-0}=(P_{lose})^A \]这同时解释了上面的初始值问题。
-
\(i = A \text{ or } B\)，这时 \((P_{lose})^i\) 就可能会出现 \(0^0\) ，我们就可以使用以下公式计算
\[a_A\text{ or } b_B=1\cdot(P_{lose})^{A\text{ or }B}\cdot1=(P_{lose})^{A\text{ or }B} \]
接下来怎么做呢？很简单，因为要判 Exusiai（b） 的积分严格大于 Texas（a） ，所以我们就是求：
这个感性理解？但是，因为 \(1 ≤ A ≤ 5×10^6, 1 ≤ B ≤ 10^{18}\) ，如果遍历一遍B就会T，所以我们把题目改一改，改成 Texas（a） 的积分大于等于 Exusiai（b） 的概率，这样就很好求吧：
\(b_j\) 可用前缀和 \(sum\) 维护。
因为我们改了题目，所以得出来得结果相反，需要用1减去：
注意需要随地大小模！建议使用 模数类。
以及，快速读入不行，还要 fread！！
T4 上网
第一眼——这不就是 拓扑 嘛！
然后就被题目数据大小秒杀了。
其实我们只需要优化：
优化 1 :
1. 对于每个 \(k_i\) ，新建一个超级点 \(t\) ，把 \(x_1∼x_{k_i}\) 连接 \(t\) ，边权设为 0
2. 再把 \(t\) 连接除 \(x_1∼x_{k_i}\) 外 \(l∼r\) 的点，边权设为 1
这样便只有 \(O(\sum_{i=1}^m r_i-l_i+1)\) 条边
也就是：
优化 2 :
我们可以建一棵线段树，每个点表示此区间的最大值。然后所有儿子连上它的父亲（因为儿子没走完，父亲就有入度，这样就可以保证父亲不会比儿子先更新，一定会先更新小区间），共 \(O(n\log n)\) 条边。我们发现 : 优化 1 的 1. 只连了 \(O(\sum k_i)\) 条边，但是优化 1 的 2. 连了 \(O(\sum_{i=1}^m r_i-l_i+1 - k_i)\) 条。
故我们可以沿用优化 1 的 1. ，改进 2.
我们发现，\(l∼r\) 被 \(x_1~x_{k_i}\) 分成了几份，每份的点是连续的（我们认为只有一个点也算连续）。我们可以让超级点 \(t\) 连接这 几 个区间在线段树的位置( 可能 1 个区间会被分成多块 )
这样就只连了 \(O(k\log n)\) 条边，然后就可以跑拓扑了。