Petrozavodsk Winter-2019. Petrozavodsk SU Contest
Contest Info
date: 2019.05.22 16:42-21:42
Solutions
B. Word Squared
题目大意：给出一个\(1\cdots n\)的排列，构造一个最小的\(m\times m\)矩阵，满足每一行每一列都至少存在一个连续子串是该排列。\(n\le 500\).
题解：将该排列复制一份接在后面，然后\(2n-2\)次rotate一位得到下一行，最后去掉第\(2n\)列即可。
D. Game X
题目大意：问所有满足如下条件的\(2\le n\le10^9\)个数字中，最多有多少对无序的二元组是同符号的：
- 不存在两个数字的绝对值相同
- 不存在等于零的数字
- 和大于\(0\)的无序的二元组恰好有\(0\le k\le10^{18}\)个
无解输出\(-1\).
题解：有解当且仅当\(\displaystyle\frac{n(n-1)}{2}\ge k\).
显然构成\(k\)的二元组，一部分是正数内部产生的，另一部分是正数与负数产生的，显然可以通过调整，让每一个负数与任意个正数产生贡献。
设正数有\(0\le x\le n\)个，则可以产生的和大于\(0\)的无序的二元组最少为\(\displaystyle\frac{x(x-1)}{2}\)个，最多为\(\displaystyle\frac{x(x-1)}{2} + x(n-x)\)个，即\(\displaystyle\frac{x(x-1)}{2}\le k\le\frac{x(x-1)}{2} + x(n-x)\)。可以解出\(x\)的范围来。
要最大化\(\displaystyle\frac{x(x-1)}{2}+\frac{(n-x)(n-x-1)}{2}\)，化简后发现是个\(A>0\)的二次函数，直接输出两个端点处的较大值即可。
F. Nightmare
题目大意：经过一些处理后题目简化为：平面上有一个长方形，沿平行与其某一条边的方向移动。平面上还有\(n\le50\)个凸多边形，当长方形的某一个顶点第一次进入多边形内部时被认为发生了一次碰撞，求第\(k+1\)次碰撞发生时长方形移动了多远，或判定不会发生这么多次碰撞。
题解：就按题意暴力就完了。
H. Employees
题目大意：一个公司有 \(n\) 个员工，每个人有一个工作时间，且互不相同。一天中他们工作的方式如下：
- 首先以任意方式排成一队，有 \(n!\) 种可能
- 有一个容量为 \(k\) 人的大厅，只要大厅没满，而队列中有人，队首就不断进入大厅
- 大厅中工作时间最短的人进去工作
- 如果大厅还有人，继续 2，否则结束
对每个人求下面两个数的积：
- 所有排列中，该人结束工作的时间减去第一个人开始工作的时间之和
- 所有排列中，工作时间比该人长，但是比该人先工作的人数之和
取模。
题解：考虑前 \(i\) 个工作的人，那么进入大厅的就是前 \(m=\min\{n,i+k-1\}\) 个人。显然这 \(i\) 个人一定是 \(m\) 个人中工作时间最短的 \(i\) 个。可以用归纳法证明。
对于每个 \(t_{i}>t_{j}\) 计算 \(i\) 在 \(j\) 前面出现多少次，那么 \(i\) 在 \(j\) 后出现的次数自然就是 \(n!\) 减去前面的次数。显然 \(i\) 要排在 \(j\) 的前面，又要是 \(\text{pos}_{j}-1\) 中前 \(\text{pos}_{j}-1-(k-1)\) 小的。再枚举一下 \(\text{pos}_{j}\) 即可容易地用组合数计算。
时间复杂度 \(\mathcal{O}(n^{3})\)。
I. Modulo-magic squares
题目大意：给定 \(n,m\)，求出每个元素都在 \([0,m)\) 之间，且每行、每列、主副对角线上元素的和模 \(m\) 均余 \(C\) 的 \(n\times n\) 方阵数量。\(C\) 在 \([0,m)\) 中任取。
题解：将方程列出来高消。可以发现，行列的 \(2n\) 个方程秩为 \(2n-1\)，可以任意删去一个。其它方程都线性无关。
\(n=3\) 时，结果为：
1 0 0 0 -1 -1 0 -1 -1 -c
0 1 0 0 1 0 0 1 0 c
0 0 1 0 0 1 0 0 1 c
0 0 0 1 1 1 0 0 0 c
0 0 0 0 1 -1 0 -1 -2 -c
0 0 0 0 0 3 0 3 6 4c
0 0 0 0 0 0 1 1 1 c倒数第二个方程，在 \(3\nmid m\) 时有唯一解；在 \(3\mid m\) 时，若 \(3|C\)，有 \(3\) 个解，否则没有解。数量上可以等价于不论如何都有一个解。另外有 \(2\) 个自由元，以及 \(C\) 可任取，答案为 \(m^{3}\)。
\(n=4\) 时，结果为：
1 0 0 0 0 -1 0 -2 0 0 -1 -2 0 -2 -2 -3 -3c
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 c
0 0 1 0 0 0 0 1 0 -1 1 1 0 1 2 2 2c
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 c
0 0 0 0 1 1 0 2 0 -1 0 1 0 1 1 2 2c
0 0 0 0 0 2 0 2 0 0 2 2 0 2 2 4 4c
0 0 0 0 0 0 1 -1 0 1 0 -1 0 -1 -1 -2 -c
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 c
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 c倒数第四个方程，在 \(2\nmid m\) 时有唯一解，答案为 \(m^{8}\)；在 \(2\mid m\) 时，有 \(2\) 个解，答案为 \(2m^{8}\)。
\(n\ge 5\) 时，观察矩阵的形式可知，行列的 \(2n-1\) 个方程已经是阶梯形矩阵，不需要消，只需考虑对角线即可。
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 c
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 c
0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 c
0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 c
0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 c
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 c
0 0 0 0 0 0 2 1 1 1 -1 0 1 0 0 -1 0 0 1 0 -1 0 0 0 1 c *
0 0 0 0 0 0 0 0 1 -1 0 0 1 0 -1 0 1 0 0 -1 1 0 0 0 -1 0 **
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 c
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 c
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 c以 \(n=5\) 为例，主对角线（*）和副对角线（**）分别被消成主元为 \(2\) 和主元为 \(1\)。那么副对角线就不需要再考虑了，而主对角线还需要用后面的行来消一下，变成
1 0 0 0 0 0 -1 -1 0 -2 0 -1 0 -1 -2 0 0 -1 -1 -2 0 -2 -2 -2 -3 -4c
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 c
0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 c
0 0 0 1 0 0 0 0 0 1 0 0 -1 1 1 0 -1 0 1 1 0 1 1 2 2 2c
0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 c
0 0 0 0 0 1 1 1 0 2 0 0 -1 0 1 0 -1 0 0 1 0 1 1 1 2 2c
0 0 0 0 0 0 2 1 0 2 0 1 1 1 2 0 0 1 2 2 0 2 2 2 4 5c *
0 0 0 0 0 0 0 0 1 -1 0 0 1 0 -1 0 1 0 0 -1 0 -1 -1 -1 -2 -c **
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 c
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 c
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 c可以看到，由于副对角线的主元位于第 \(2n-1\) 列，而后面的行主元更靠后，因此主对角线第 \(n+3\) 列的自由元的系数一定不会被消，因而是 \(1\)。从而与 \(n=3\) 的情况类似，不论如何，答案都是 \(m^{n^{2}-n}\)。
J. Count the Sequences
多少年前的原题了。。。还是个二阶原题。。。太牛批了
