JSOI 王国里有 $N$ 个机场，编号为 $1$ 到 $N$。从 $i$ 号机场到 $j$ 号机场需要飞行 $T_{i,j}$ 的时间。由于风向，地理位置和航空管制的因素，$T_{i,j}$ 和 $T_{j,i}$ 并不一定相同。 此外，由于飞机降落之后需要例行维修和加油。当一架飞机降落 $k$ 号机场时，需要花费 $P_k$​​ 的维护时间才能再次起飞。 JS Airways 一共运营 $M$ 条航线，其中第 $i$ 条直飞航线需要在 $D_i$ 时刻从 $X_i$ 机场起飞，不经停，飞往 $Y_i$ 机场。 为了简化问题，我们假设 JS Airway 可以在 $0$ 时刻在任意机场布置任意多架加油维护完毕的飞机；为了减少飞机的使用数，我们允许 JS Airways 增开任意多条临时航线以满足飞机的调度需求。 JYY 想知道，理论上 JS Airways 最少需要多少架飞机才能完成所有这 $M$ 个航班。

给出方程： $\sum_{i=1}^nx_i=s$ 其中 $f_i \le x_i \le g_i(1 \le i \le n)$。 求这个方程组的解的个数 $ans \% 1000000007$。

问题

题目描述题目传送门思路首先有一个结论：删除边后的最短路一定是在最短路上跑一段，然后跳出最短路，然后再跑一段。换言之，就是不在最短路上跑的路径一定是一段连续的路径，不会存在两段及以上（如果两段相等，假设选择原最短路上的路径）。证明：这个结论是我猜出来的，现在给出简要证明。记 dis⁡(i)\opera

费马小定理 欧拉定理 扩展欧拉定理

题目描述题目传送门思路看到 $n \le 10^6$，显然会有一些结论。结论1能打败人最多的人可能胜利。证明：假设打败人最多的人（称其为 Cms）不可能胜利，那必定有人（下文称其为石老板）可以打败他和他所有能打败的人，否则可能出现 Cms 打败的人干掉了石老板，然后 Cms 干掉了他，取得胜利。为了

题目传送门思路对于一个字符串 $s$，$z_i := |\operatorname{LCP}(s,s[i:])|$，即 $s$ 从 $i$ 开始的后缀与 $s$ 的最大匹配。暴力计算 $z$ 函数是 $O(n^2)$ 的，考虑将计算的 $z$ 函数用起来。我们顺次计算 $z$ 函数，假设现在需要计

题目描述题目传送门思路这题黑是恶意评分吧考虑 dp，先想状态怎么设。很容易想到的第一种 dp，假设 $dp_{i,j}$（$j \in \{1,2\}$），表示第 $i$ 个人吃了左边（$j = 1$）或者 右边（$j = 2$）的食物，可是这样似乎没有什么转移关系，所以做不了（~~或者我太菜了不会

虚数我们定义 $i = \sqrt{-1}$ ，称 $i$ 为虚数单位。

题目描述题目传送门1题目传送门2给定长度为 $n$ 的序列 $a$。$m$ 次询问。每次询问给出 $p,k$。您要不断地执行操作 $p\gets p+a_p+k$，直到 $p>n$ 为止。询问的答案为操作次数。$1\le n,q\le 10^5$，$1\le a_i\le n$。思路Algor