今天是2023/10/19，停课第四天，整理一下思路吧……
拓扑排序、数学
拓扑很简单，关键是这个分数到底会多大。
观察到题目中有限制m最大是10，最多经过10个中转点，出边小于等于5，这些限制很明显就是规定了p，q的范围。
前者说明总水量最多是10，而每次分流都只是进行了分配水量的操作，总水量不变，所以过程中的每个节点的水量都不大于总水量。
\[\frac{p}{q}\le10,p\le10q \]算出q的范围，乘10倍就是p的范围。
考虑只分流了一次，对于一个节点，他会加上所有入边来的流量。
如果不约分，最多有100000条边，分母最大是\(5^{100000}\)，写高精度都难受。
考虑通分之后用最简分母q算，相同的分母不会让q变大，不同的分母会让q变成二者的最小公倍数。
所以q最大是1,2,3,4,5的最小公倍数，也就是60。
分流一层，q最大是60，换言之，我们可以把分母是6,15，……都变成分母是60的分数。
下一次分流，\(w_1=\frac{...}{60}+\frac{...}{60\times5}+...\)，点自己本身可能被分流过一次，分母是60，其它来的点都是第二次分流的点，分母也都是60，把\(\frac{1}{60}\)提取出来，新的分母最大也是60。
所以二层分母最大是\(60^2\)。
……
中转十次，相当于分流11次，分母最大是\({6^{11}}{10^{11}}\)。
然后q和10q都在__int128范围内，搞定。
其实本来是想分别记录两个q1,q2，然后分母是q1*q2，每次只给较小的那个乘上，后来发现好像不行。
如果是高精度，写更相减损术可能会TLE，观察到分母都是若干个1,2,3,4,5的成绩，分解质因数只有2,3,5。
所以每次分子分母尝试同除2,3,5，……。
复杂度小于\(O(log_2Q+log_3Q+log_5Q)\)。
高阶差分
适用于：给一段区间加上一个数列，并且这个数列若干次差分之后可变成常数列，注意每阶差分都要在r+1减去前缀和消除影响。
然后就是组合数有一个递推式子\(C(i,j)=C(i-1,j-1)+C(i-1,j)\)，得到\(C(i,j)-C(i-1,j)=C(i-1,j-1)\)，差分一次的数组可以写成组合数的形式。
写多几行找规律就行了……
标签：10,frac,水量,笔记,60,分流,分母 From： https://www.cnblogs.com/zhangchenxin/p/17773944.html