原文出自珞珈山水BBS
这次比赛我出了3道题目: A题Exchange, D题Matrix, E题Necklace.

Exchange

出这道题目主要目的是测试组合数学中容斥原理方面的知识。
这道题目在赛前被分为中等难度题目，但是比赛中似乎并没有太多的队伍交这道题目。
我写的标程是使用棋盘多项式来求解，比如题目中的样例数据可以这样构造棋盘：

                a1   a2   b1   c1   c2   c3
        HUST1   0    0    1    1    1    1
        HUST2   0    0    1    1    1    1
        CUG1    1    1    0    1    1    1
        CCNU1   1    1    1    0    0    0
        CCNU2   1    1    1    0    0    0
        CCNU3   1    1    1    0    0    0

amath
其中行代表某学校的确定的一个交换生名额，列代表每一个学生，矩阵值为0代表行的那个名额不能分配给列的这个学生，1代表可以。另外由于事实上一个学校的多个名额是没有区别的，所以最后算得的棋盘排列数要除以每个学校名额数阶乘的累乘。

Matrix

出这道题目的目的是测试基本编程能力。没有卡时间，基本上差不多的方法都能过。
这道题在赛前估计中列为第3简单的题目，事实上这道题目在比赛中的AC次数正好排第3。
我的标程的思路是若当前不是矩形，则推导出哪些邻近字母一定包含在解中，然后迭代处理直到为矩形。

Necklace

这道题目是测试模线性方程组及贝恩赛特引理的相关知识。
在赛前和C题及H题一同被列为难题，令人伤心的是比赛中没有特别多的队去提交。
这道题的主要工作并不在于模线性方程组及贝恩赛特引理，而是模型的提取。
所以对于模线性方程组及贝恩赛特引理的相关内容不做介绍，请参阅其他资料。
下面给出我的标程的思路的粗略描述和并不十分详细的证明：
定义1: 选定一个固定位置的珠子开始对所有珠子进行编号, 从`0`到`n-1`. 定义`01`向量`s0,s1…sn-1`为项链的图像, 其中`si = 1`代表i号珠子为黑色, `si = 0`代表`i`号珠子为白色.
由题意得到方程组`L`:

`k_{0,0} * x_0 + k_{0,1} * x_1 + … + k_{0,n-1} * x_{n-1} = a_0 (mod 2)`
`k_{1,0} * x_0 + k{1,1} * x_1 + … + k_{1,n-1} * x_{n-1} = a_1 (mod 2)`
`…`
`k_{n-1,0} * x_0 + k_{n-1,1} * x_1 + … + k_{n-1,n-1} * x_{n-1} = a_{n-1} (mod 2)`

其中`a`向量代表目标项链图像. `k_{i,j}`代表`t`秒变换的变换系数. `x`向量代表`t`秒前的图像.
结论1 : 如果目标项链的图像旋转`d`个单位后的图像不变, 那么在解空间中的任意图像旋转`d`个单位也在解空间中.
证明: 对于解空间中的任意图像(解图像), 将其旋转`d`个单位, 则`t`秒后对应的图像即为原图像`t`秒后的图像(目标图像)旋转`d`个单位. 由于目标项链旋转`d`个单位后的图像不变, 知解图像旋转`d`个单位也是解图像.
定义2 : `G = {使得目标项链图像旋转后图像不变的置换}`, `@`为置换乘法.
结论2 : `<G, @>`成群.
证明: 幺元存在, 可结合性, 逆元的存在等均可参照置换的性质得到. 下面仅给出`G`在`@`下封闭性的说明.
封闭性:对于`d1, d2 in G`, 若`d1@d2 !in G`且`d1 in G`, 易得`d2 !in G`.
定义3: 经旋转后相同的图像称为等价图像类.
结论3: 等价图像类是等价类.
证明: 两图像经旋转后相同的这个关系是自反的, 因为一个图像是其自身旋转`0`的单位得到的; 这个关系是对称的, 因为一个图像可由由其旋转`d`个单位得到的图像旋转负`d`(反方向)个单位得到; 这个关系是传递的, 因为`A`旋转`d1`个单位得到`B`, `B`旋转`d2`个单位得到`C`, 则`A`旋转`d1+d2`个单位得到`C`. 所以上述关系为等价关系, 故其导出的等价图像类为等价类.
结论4: 解空间中等价图像类的个数 = `(sum(di in G)[f(d_i) * f_i(n/|d_i|)])/|G|` .(其中`f(d_i)`为解空间中在置换`d_i`作用下图像不变的解数, 可通过求其对应的线性方程组增广矩阵的自由度算出. 之前提及的方程`L`对应于`G`中的幺元)。
证明：参照贝恩赛特引理.

下面说一下第一次作为出题人的感受。
自己的题目被人AC是很happy的，所以D题让我happy了很久，哈哈，但是遗憾的是一开始数据有点小问题会使得一个字符一个字符读入的程序不能 AC, 好在很快改正了这个问题。
A题在1个小时的时候也让我happy了一下，第一次提交这道题的队是一个高中生队伍，第一次提交是TLE, 我立刻用他们的程序跑了一下数据发现是对的但是有一些超时，果然之后他们立刻AC了。
这次比赛我们还是出了很多问题，比如数据和部分题面，不过有了这些经验教训相信决赛不会再出现这样的问题了！
endamath