人傻自带大常数+论对着数据优化代码的丧病

$$ \begin{align} f(n)&=\sum_{i=0}^n\sum_{j=0}^i S(i,j)*2^j*(j!)\\ &=\sum_{i=0}^n\sum_{j=0}^n S(i,j)*2^j*(j!)\\ &=\sum_{i=0}^n\sum_{j=0}^n 2^j*(j!)* \frac 1{j!}*\sum_{k=0}^j(-1)^kC_k^j(j-k)^i\\ &=\sum_{i=0}^n\sum_{j=0}^n 2^j*\sum_{k=0}^j(-1)^{j-k}C_k^jk^i\\ &=\sum_{i=0}^n\sum_{j=0}^n 2^j*\sum_{k=0}^j(-1)^{j-k}*\frac{j!}{k!(j-k)!}*k^i\\ &=\sum_{j=0}^n 2^j*\sum_{k=0}^j(-1)^{j-k}*\frac{j!}{k!(j-k)!}*\sum_{i=0}^nk^i\\ &=\sum_{j=0}^n 2^j*j!*\sum_{k=0}^j\frac{(-1)^{j-k}}{(j-k)!}*\frac{\sum_{i=0}^nk^i}{k!} \end{align} $$
其中$\sum_{k=0}^j\frac{(-1)^{j-k}}{(j-k)!}*\frac{\sum_{i=0}^nk^i}{k!}$交给我们伟大的NTT处理，令$a_i=\frac{(-1)^{j-i}}{(j-i)!}$，$b_i=\frac{\sum_{i=0}^nk^i}{k!}=\frac{i^{n+1}-1}{(i-1)*i!}$，$c_i=\sum_{k=0}^ia_k*b_{i-k}$，则$ans=\sum_{j=0}^n 2^j*j!*c_j$。

zkw

Orz

tb_kp流大法吼

我猜是tb_kp流

输出K不对1000000007取模。。顿时感到一股深深的恶意

我猜是Spfa

我猜是平衡树套主席树上的网络流

我猜是数论。

我猜是双层for循环

我猜是辛普森

我猜是网络流

回复 @若连自己也无��相信，那指望谁能信 :
我瞧DBW太神了

回复 @cstdio :
梦迪的代码有点小问题，他代码里面联通块的大小不是正确的，可能会影响复杂度。正确的做法应该在每次找到根之后再次dfs求子树大小。如果某次被数据卡掉了就尴尬了。

话说我记得有个这个条件的，但是我重新看了看，题面上却没有写。似乎是老师临场说的。
对于条件的疏忽，我表示非常抱歉。

开心的15min无脑写完，却怎么都不过样例，想%萌帝的代码，却发现和自己的做法不一样。
就这样开始纠结是不是自己读错题了或者算法有问题。。
20min后才发现：每次跑最大流的时候忘记把上一次的flow清零了。。

分治+网络流+最大生成树

费马合性检验真TM好写！