费用流的对偶建模

考虑最大费用循环流的标准线性规划建模: 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_{...
Click to read more ...

FFT mod 1e9 + 7

在做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来做整数的卷积,可以使用一些技巧来继续减...
Click to read more ...

Trivial matters

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

北航第十一届程序设计竞赛网络预赛题解

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,...
Click to read more ...

TC SRM661~670

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操作,以及...
Click to read more ...