2016-S03-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
比赛链接: http://10.71.10.90/sfiction/ranklist/2016_Asia_Beijing/ranklist.htm
== 流水账 ==
[http://www.cc98.org/dispbbs.asp?boardID=329&ID=4666566 2016 北京赛区小结 by sfiction @Siunaus]
== 总结 ==
== 题解 ==
DEF 略去不表。
=== A. Harmonic Matrix Counter [sfiction] ===
以第一行状态为变量，逐行推出每个位置关于第一行的线性组合，若矩阵合法，则n+1应当为全0。要求出所有解，可以对n+1行对应的m个方程消元。设秩为K，则有m-K个自由元，共2^m-K^个解。回代后，所有非行首的变量即为自由元，对应列非零项是其影响的其他变量。根据k的二进制表示将各列异或即可。需要注意的是为了满足字典序要求，消元时列要从右往左处理。O((n+q)m^2^/64)。
=== C. Asa's Chess Problem [Akalm] ===
以行、列整体为点，有交换关系的连边，跑上下界费用流。
sfiction: 行列的和可以看做是它们的流量，pair的交换由于是同行或者同列，可以视为行间或列间1个单位流量的流动。因此以行列为点，pair交换为(low=0,high=1,cost=1)的边。源到点连上下界均为原有流量的边。点到汇连题中给定上下界的边。因为是费用流，这两类边的下界可以改用无穷小费用来约束。
=== G. A Triangle Puzzle [sfiction] ===
将第二个三角形中元素逐行逐个标为1-n，第一个三角形中相同元素取相同标号，按标号从大到小变换到相应位置，则最后只可能是1和2位置不同。对互不相同元素的排列而言，存在两个等价类。对有相同元素的情况，通过交换任意两个相同元素，可以简单变换到另一个等价类。按从下往上，从右往左的顺序放置，j>1的情况很容易构造。j=1的情况需要先将a[i][2]转到a[i][1]，再把目标数放到a[i-1][1]。O(n^3^)。
=== H. A New Ground Heating Device [JTJL] ===
二分答案，求K重圆并。使用格林公式。对于重合的圆，用编号大的屏蔽编号小的（防止重复计数）；对于存在覆盖关系的圆，大圆处忽略，在小圆处处理。
=== I. A Boring Problem [sfiction] ===
将排列A(x,k)视为k次多项式，幂即可表示为排列数的线性组合，系数为第二类斯特林数。这可以在O(K)时间内将Sigma(ai^K^)变换为Sigma((ai+1)^K^)。于是可以从前往后统计一遍。O(kn)。
=== K. JiLi Number [sfiction] ===
由归纳知[10^k-1^,10^k^-1]计数过程中max(i-s)出现在10^k^-1，且等于(10-k-1)*10^k-1^-1。当k=9时，max(i-s)=-1，因此>=2E9时无解，第83个解之后则s占优，因此总共只有83个解。比赛链接: http://10.71.10.90/sfiction/ranklist/2016_Asia_Beijing/ranklist.htm
流水账
2016 北京赛区小结 by sfiction @Siunaus
总结
题解
DEF 略去不表。
A. Harmonic Matrix Counter [sfiction]
以第一行状态为变量，逐行推出每个位置关于第一行的线性组合，若矩阵合法，则n+1应当为全0。要求出所有解，可以对n+1行对应的m个方程消元。设秩为K，则有m-K个自由元，共2m-K个解。回代后，所有非行首的变量即为自由元，对应列非零项是其影响的其他变量。根据k的二进制表示将各列异或即可。需要注意的是为了满足字典序要求，消元时列要从右往左处理。O((n+q)m2/64)。
C. Asa's Chess Problem [Akalm]
以行、列整体为点，有交换关系的连边，跑上下界费用流。
sfiction: 行列的和可以看做是它们的流量，pair的交换由于是同行或者同列，可以视为行间或列间1个单位流量的流动。因此以行列为点，pair交换为(low=0,high=1,cost=1)的边。源到点连上下界均为原有流量的边。点到汇连题中给定上下界的边。因为是费用流，这两类边的下界可以改用无穷小费用来约束。
G. A Triangle Puzzle [sfiction]
将第二个三角形中元素逐行逐个标为1-n，第一个三角形中相同元素取相同标号，按标号从大到小变换到相应位置，则最后只可能是1和2位置不同。对互不相同元素的排列而言，存在两个等价类。对有相同元素的情况，通过交换任意两个相同元素，可以简单变换到另一个等价类。按从下往上，从右往左的顺序放置，j>1的情况很容易构造。j=1的情况需要先将a[i][2]转到a[i][1]，再把目标数放到a[i-1][1]。O(n3)。
H. A New Ground Heating Device [JTJL]
二分答案，求K重圆并。使用格林公式。对于重合的圆，用编号大的屏蔽编号小的（防止重复计数）；对于存在覆盖关系的圆，大圆处忽略，在小圆处处理。
I. A Boring Problem [sfiction]
将排列A(x,k)视为k次多项式，幂即可表示为排列数的线性组合，系数为第二类斯特林数。这可以在O(K)时间内将Sigma(aiK)变换为Sigma((ai+1)K)。于是可以从前往后统计一遍。O(kn)。
K. JiLi Number [sfiction]
由归纳知[10k-1,10k-1]计数过程中max(i-s)出现在10k-1，且等于(10-k-1)*10k-1-1。当k=9时，max(i-s)=-1，因此>=2E9时无解，第83个解之后则s占优，因此总共只有83个解。