考虑最大费用循环流的标准线性规划建模： Maximize: $\sum_{i \in E}{cost_i \cdot f_i}$ 对每条弧$i$有 $0 \leq f_i \leq cap_i$ ，$cap_i$ 表示这条弧的容量，$f_i \geq 0$。 对于每个点$x$有流量平衡: $\sum_{u_i = x}{f_i} - \sum_{v_i=x}{f_i} = 0$ 共有$|V|+|E|$个限制，对偶后，设前$|V|$个限制对应的变量为$a_i$，后$|E|$个限制对应的变量为$d_i$，则变为如下线性规划模型： Minimize: $\sum_{i \in E}{cap_i \cdot d_i}$ 对每条弧$i$有 $a_{v_i} - a_{...

在做FFT mod 任意质数一个传统的方法是利用NTT和CRT，这样比较适合一些小模数的题目，因为要保证$NP^2$在64位整数范围内，不然将需要更高精度的整数。 但最近学习了一种比较Tricky的方法，假设模数为$P$，设$M=\lceil \sqrt{P} \rceil$，可以将一个多项式$F(x)$拆成两个多项式$F_{0}(x),F_{1}(x)$，其中： 这样就能把多项式每一项系数的值域变成$\sqrt{P}$级别，用double实现的复数做FFT精度就不会爆炸了。 如果要求两个多项式$F(x),G(x)$的卷积： 这样只需似乎只用做7次FFT，效率应该比NTT要好，然而这只是一个开始。 由于这里需要用复数的FFT来做整数的卷积，可以使用一些技巧来继续减...

题解幻灯片地址

又是一年ACM-ICPC Regional结束的时期，稍微总结一些这个赛季吧，感觉这个赛季还是有不少收获的。 年中在马拉喀什的WF失利了，失利的非常彻底，这也让我们队伍思考了一下该如何，不过也没经过多少讨论，TheWaySoFar还是继续保留了下来。训练应该也是从暑期集训开始恢复的，其实感觉这一次暑期集训的效果并不是很好，期间的几次训练我还因为要面试以及参加百度之星和计蒜客的onsite还翘了。赛中出现的问题也没有积极地进行总结反思，最后使得到网络赛的时候队伍出线了很多问题。不过这也是我能参加的最后一次暑期集训，在其他事情上还是下了不少心血的。尤其是看到还有今年刚入校的2015级的三个小同学被我们忽悠愿意舍弃暑期到学校参加集训，同时还有很多有实力的年轻队伍，作为一个还有不到一年就要滚...

A. 模式 计算机学院是6系，软件学院是21系，对于输入的学号只需要判断$\lfloor \frac{id}{10000} \rfloor$是多少即可。 B. 并联变阻器 题意即统计满足$a,b\le N$且$\frac{ab}{a+b}$是整数的二元组$(a,b)$的个数，条件也即$a,b\le N$且$(a+b)|ab$。 令$r=\gcd(a,b)$，则有$\gcd(\frac{a}{r},\frac{b}{r})=1$，再令$a=rx,b=ry$，那么$(a+b)|ab$ 可以表示为$r(x+y)|r^2xy$，也就是$(x+y)|rxy$。 由于$x$与$y$互质，所以$\gcd(x+y,x)=\gcd(x+y,y)=\gcd(x,y)=1$，$(x+y)$与$x,...

SRM661 Easy 求出1~n的LCM，拿每个质数次幂的大于n的最小倍数更新答案。 Medium 单独考虑每个点，如果一个点前面有i个点，啥都不连方案为K，如果连因为不能同色方案为i*(K-1)，所以答案为$\Pi_{i=0}^{N-1}(K + (K-1)i)$。 Hard 没看 SRM662 Easy 大概是排成先上升后下降的圈。 Medium 设$f[i][j]$为$i$个节点，全距离和模$m$为$j$的有根树的最小全距离和。因为是有根树，转移则是在某个节点上再连一棵有根树，如果之前那棵有根树大小为$x$，则新的边会被走$x(n-x)$次。 时间复杂度为$O(n^2m^2)$ SRM663 Easy 按照目标串与初始串的B数量之差可确定做了多少次B操作，以及...