怎么暴力就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 :
我也觉得这个太神奇了，第一个测试点搞得我调了半天，突然发现不合逻辑

为什么就WA了两个点。。。

POJ2342

卡特兰数%%%%%%%%%

回复 @sxysxy :
膜拜sxy的公式！其实
\[ \sum_{i=1}^{n} {[ \frac{n}{i}]} \] = \[ \sum_{i=1}^{n} {d[i]} \]

回复 @叶子の宿敌 :
所谓好几种解法，是好几种方法求lca。
当然还可以树形dp

%%%

@ soy juice 喜闻乐见

衷心的祝愿出题人身体健康

样例好评

第一次被卡常70
+读入优化80，第三个点本地数分钟算不出结果。
+当前弧优化AC。
原来这个优化这么强...

循环水过,yeah！