【题解】CTT 2019 Day 2

• A. 循环序列
• B. Matrix
• C. 杀蚂蚁简单版

A. 循环序列

即求 \(\sum\limits_{i=0}^{c}{k\choose m+in}\)，即 \(\frac{1}{n}\sum\limits_{j=0}^{n-1}\sum\limits_{i=0}^{k-m}{k\choose m+i}\omega_{n}^{ji}\) 。对于 \(\sum\limits_{i=0}^{k-m}{k\choose m+i}\omega_{n}^{ji}=\omega^{-mj}\sum\limits_{i=m}^{k}{k\choose i}\omega_{n}^{ji}\)，因此实际要解决的是 \(f(x)=\sum\limits_{i=0}^{m-1}{k\choose i}x^i\) 的多点求值问题，用 Bluestein 完成即可。

注意到 \(\omega_{n}\) 作为方程 \(x^{n}\equiv 1\pmod {p}\) 的某个解是肯定存在的，因为 \(n\mid p-1\) 。

B. Matrix

判掉负数和行列和不一样的情况，剩下的情况必然有解。

于是只需要每次找出一组排列使得对应位置都非零即可。行列连边二分图匹配，每次抛出解后至少一个位置变成 \(0\) 不可再用，此时退掉这一条匹配边即可。时间复杂度 \(O(n^4)\) 。提交记录：Submission #77954 - QOJ.ac 。

C. 杀蚂蚁简单版

通过反复合并式子或者转化式子，最后可以得到一个这样的问题：枚举链上点 \(u\) 算得与 \(s\) 的 LCA \(t\)，权值是一个关于 \(t\) 的定值，以及一个关于 \(u\) 的定值。只要简单的预处理后求 LCA 即可。