2018 ACM-ICPC China Shanghai Metropolitan Invitational Contest
Problem A
Solved by zerol. 01:21 (+)
题意：求一条直线，至少经过 N 个点中的 N * k 个点，$(0.1 \leq k \leq 0.9)$。
题解：随机挑两个点，如果有解，那么有 $\frac{1}{k^2}$（最坏情况要随机几百次） 的概率恰好落在答案所在的直线上。当然这是不考虑点重复的情况，事实上这样就能 AC。但是比如 n = 10000，k = 0.1，有 998 个点在同一个点上，另外恰好有一组 1000 个点共线，那么概率会很低。所以如果随机到的两个点一样的话，必须重新在剩下的点里随机，即便这样命中率也只有约 $0.1 \times 0.1 \times 0.0002$。
另解：更好的做法是随机一个点，统计其他点的斜率，这样就不会有点重复的问题了，随机次数最多也只需要几十次。
Problem B
Solved by ultmaster. 00:10 (+)
求完美数分解，温暖的签到。
Problem C
Upsolved by ultmaster.
EOJ 3407。样例都没改。
ultmaster：因为做过，所以判断在现场不能做。
重现赛：上了两个板子过了。
Problem D
Solved by kblack. 00:36 (+1)
裸几何规律，温暖的签到。
Problem E
Upsolved by ultmaster.
题意：有一种循环回文子串：把字符串的某一个后缀移到前面若构成的新字符串是一个回文串，就称循环回文串。求原字符串在修改最多两个字符的情况下的最长循环回文子串，要求长度为奇数。
题解：以一个点为中心，用二分 + hash 的方法，可以求出以该点为中心，修改最多 0 个、1 个或 2 个的最长回文子串。然后把这个信息转化成以 $i$ 结尾的修改 0 个、1 个或 2 个的最长回文奇数串；以 $i+1$ 为开头的修改 0 个、1 个或 2 个的最长回文偶数串。可以发现循环回文串就是前面一个奇数和后面一个偶数拼起来。所以枚举前后的修改次数，两边拼起来就可以。奇偶可以互换，所以还要倒过来再做一遍（偶数回文串如果结果偏左或者偏右的话，倒过来的时候还要偏移）。注意也有可能只有一个奇数，如果姿势不好可能要特判。
ultmaster：这题我要背大锅。kblack 的 hash 敲了半天终于差不多敲对了已经意识模糊了。然后我贡献了一个假得不行的做法，还提出了一个其实完全用不到的 API 需求。然后比赛的剩余时间在就要丢掉奖杯的绝望和轮换调试 API 和假做法中度过。其实如果 kblack 的意识还在线的话，或许是有希望的。但是或许时间也不大够了。赛后进行了对拍，花了一个半小时修复了若干个 bug，才艰难地通过随机数据。
本题以加入 EOJ 豪华午餐：3626。（事后发现这道题其实是原题的一个加强版，原因是题目有歧义。。。）
重现赛：所以是切掉一段剩下来的组成回文串咯？我真是艹了。辣鸡 kuangbin 还我下午！
补充：就算改了这题还是假的，比如 zywvucdeedcaaaaaaaaaaaaaaraaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaa 正确答案是 57（删左边 5 个），但是 AC 代码输出 51（对 cdeedc 视而不见）。
Problem F
Solved by ultmaster. 01:06 (+1)
题意：有一个网格，然后有若干个圆去覆盖。求没有被覆盖到的点的数量。
题解：由于询问数量少、行列数量也不大，直接枚举行，然后在列上标记覆盖范围就好了。ultmaster 一开始想上线段树，然后经过 zerol 的提醒，发现线段树也不要。只要一个扫描线就好了。然后扫描线也调不出来（到底是有多惨？），甚至还打印了，最后发现 $n$ 和 $m$ 搞错了。然后修 bug 修了一半（初始化没修），WA1。
Problem G
Unsolved.
Seems similar to EOJ 2842.
Problem H
Solved by kblack. 03:01 (+1)
题意：区间平方膜 2018，区间求和。
题解：一个数不断平方膜 2018，最多 4 次后就会进入长度是 6 的约数的循环节，于是将序列分为两类数分别考虑。 对于循环内的数，直接记录当前即平方5次内的所有和，平方操作即是对数列的位移操作，可以懒标记维护。 对于循环外的数，暴力递归到叶子节点，手动平方，一旦进入循环就删掉特殊标记，转化为上一种维护方式。
Problem I
Solved by zerol. 03:34 (+1)
题意：给一个矩阵，每次可以对一个数 +1 或 -1（不能为负），问最少几次使得每行之和相等，每列之和相等。
题解：枚举每行的和，然后建图，每行以及每列是一个点，行（列）如果不够和就连源（汇），超过则连汇（源），行列之间的双向边费用均为 1，有一个方向（代表 -1）有容量限制（因为元素不能为负）。对每行的和的所有可能值进行三分跑费用流。
zerol: 鉴于数据范围很小，kblack 给出了指导性意见——网络流，在 ultmaster 读错题的情况下给出了正确的建图方法，然后蜜汁 TLE，然后加了个三分就过了。然而还有更加简单的做法。
Problem J
Solved by ultmaster. 02:05 (+)
题意：求 $n$ 以内能被各位数字之和整数的数的数量。
题解：枚举各位数字之和 $p$，然后维护两个量：一个是当前数模 $p$，还有一个是当前各位数字之和。最后可行条件是当前数为 0 且各位数字之和等于 $p$。
ultmaster: 惊！全队居然没有一个人会数位 DP。kblack 说数位 DP 复杂度不对，大家都信以为真。在没有题可以上的情况下，ultmaster 上机打了个暴搜，发现答案多得一批。绝望。然后经过 zerol 提醒，发现好像不同测试数据之间的计算是可以重用的！然后写得倒是很快。通过跟表手动对拍发现了一个 bug，避免了一个 WA。
Problem K
Solved by kblack. 00:24 (+)
裸矩阵乘法，温暖的签到。
Problem L
Upsolved by ultmaster.
题意：求 $b_i = \sum_{j=0}^{N-1} (a_j (4^i \cdot p + q)^j)) \bmod 200003$。
题解：跟 kblack 一致卡在了最后一步。然后厚颜无耻地问邝老师要了标程。
所有的奥妙大概可以用下面的式子全部涵盖：
- $ans_{i} = \sum_{k=0}^{N-1} (p \cdot 4^i)^k / k! \cdot c_{k}$.
- $c_{k} = \sum_{j=k}^{N-1} j! a_{j} \frac{q^{j-k}}{(j - k)!}$.
- $t1_{k} = p^k c_{k} 2^{k^2} / k!$; $t2_{k} = 1 / (2^{k^2})$.
- $ans_{i} = \sum_{k=0}^{n-1} t1_k t2_{i-k}$.
特别说明一下最后一步：由于要用到「负」的东西（$i-k$ 可以是负的），把负的东西存在最后就好了，由于这好像是一个循环的（具体原理也没怎么搞清楚）。
有一个略有点恶心的事情是要上一个任意模 NTT 的板子。感谢邝老师，以收入模板库。
本题以收入 EOJ 3627。