nlog^2的慢成翔，不过好在只有45行，非常好调

priority_queue莫名E

贪心。。贪心

回复 @Janis :
hujingyuan？？

……

千万不要用cin，会超时......

回复 @卜卜 :
30000000还是可以承受的吧。而且出题人没造极限数据，达不到$O(\sqrt n)$

回复 @卜卜 :
可是这个题的复杂度就是$O(nlogn)$啊，实际上是达不到这个复杂度上限的，但是由于有取模和CRT所以常数比较大，100W大概4s差不多吧。

%%%

根号算法为啥能过啊？？ 这么多零一看就感觉会TLE 感觉只能用Pollard_Rho诶

CDQ配合树剖套线段树套半平面交是错的吗？
出题人真是丧心病狂，直接把long long的半平面交溢出了……

建图最开始想错了。。。
最后把超级源点到主飞行员的流量设为1，主飞行员到副飞行员的流量设为正无穷，副飞行员到超级汇点的流量为1，
结果最开始写反了。。。。。

怎么暴力就AC了勒？？？ 感觉复杂度不对呀 nlogn 100W 应该过不了啊

我们老师讲用广搜做，看了评论后，找了Floyd的算法看了看，太神奇了....
感觉像自己装逼的逼格都上升了一个档次......

过程曲折……并且被坑的好惨

\begin{align*} \sum_{i=1}^\infty\prod_{j=1}^k\frac{1}{ik+j}&=(k-1)!\sum_{i=1}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\frac{1}{ik+j} \\ &=(k-1)!\sum_{i=1}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\int_0^1x^{ik+j-1}dx \\ &=(k-1)!\sum_{i=1}^\infty\sum_{j=0}^{k-1}(-1)^jC_{k-1}^j\int_0^1x^{ik+j}dx \\ &=(k-1)!\sum_{i=1}^\infty\int_0^1(1-x)^{k-1}x^{ik}dx \\ &=(k-1)!\int_0^1\sum_{i-1}^\infty x^{ik}(1-x)^{k-1}dx \\ &=(k-1)!\int_0^1\frac{(1-x)^{k-1}}{1-x^k}dx \\ &【前方高能预警】 \\ &=k!\int_0^1\sum_{j=1}^{k-1}\frac{(1-\varepsilon^{-j})^{k-1}}{1-\varepsilon^j x}dx &(\varepsilon=e^{\frac{2i\pi}{k}}) \\ &=-k!\sum_{j=1}^{k-1}\frac{(1-\varepsilon^{-j})^{k-1}}{\varepsilon^j}\ln(1-\varepsilon^j) \\ &=-k!\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\ln(1-\varepsilon^j) \\ &【什么？你以为这就完了？图森破】 \\ &=k!\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\sum_{i=1}^\infty\frac{\varepsilon^{ij}}{i} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\varepsilon^{ij} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{j=1}^{k-1}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l\varepsilon^{jl+ij} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l\sum_{j=1}^{k-1}\varepsilon^{j(i+l)} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l(-1+[(i+l)\bmod{k}=0]k) \\ &=k!\sum_{i=1}^\infty\frac{1}{i}(\sum_{l=0}^{k-1}(-1)^{k-l}C_{k-1}^l+k(-1)^{(i-1)\bmod{k}}C_{k-1}^{(i-1)\bmod{k}}) \\ &=(k-1)!\sum_{i=1}^\infty\frac{(-1)^{(i-1)\bmod{k}}C_{k-1}^{(i-1)\bmod{k}}}{i} \\ &=(k-1)!\sum_{i=1}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\frac{1}{ik+j} \\ &=\sum_{i=1}^\infty\prod_{j=1}^k\frac{1}{ik+j} \\ &【登登登！成功推回来啦！】 \end{align*} 所以问题来了，这个式子还有更简洁的结果嘛？

写了一个上午的最小费用最大流终于写出来了。。。。。。。
跪在了路径上。。。。。。。。。

咳咳

回复 @RP :
我也觉得这个太神奇了，第一个测试点搞得我调了半天，突然发现不合逻辑