总结

预期：100+70+[20~? ]+0=[190~? ] 实际：50+95+0+0=145

比赛过程

由于上一天的经历，我决定先降低自己的预设分数，确保能获得 100pts 以上即可，甚至做好达不到 100pts 的准备。

今天的 T1 明显难于昨天 T1，爆搜的复杂度有点错啊，加上剪枝，在加个 map 标记一下，大样例跑了 30ms，这对吗？由于只有一个大样例并且很水，加上我认为这只是 T1，所以并没有在继续管他，往下继续做，此时过去 30min，预期得分 100pts。

T2 当 \(n\) 是偶数似乎比较简单，直接 \(dp\) 难道就行了？写，过了大样例。接下来轮到 \(n\) 是奇数，想着先写下暴力，这样方便验证正确性，因为大样例是偶数。问题是我的暴力写假了，并且始终找不到问题！虚空调试好久，此时已经过去了 1h10min，预期得分 120+pts。

往后看看吧！T3 博弈论有点神秘啊，想了一想，好像可以分析出一些性质，先搁置一下吧，先去看 T4。

T4 题面怎么这么猎奇，被吓到了，好像要用串串的技巧，算了，先不管了，回去做一下 T2,T3。

T3 似乎比 T2 好做？思考思考，推一推，发现了关键性质，但似乎在 2 进制上的判定上有些小问题（这是后话），为了验证结论开始打表，然后开始写，由于脑残没有想到怎么区间数颜色，只能乱搞，搞完之后 只剩 55min 了，预期得分 140+pts。

T2 好像又发现写神秘性质，加上些神秘预处理好像可以 \(O(n^2\log n)\)，但是似乎来不及了，写了个 \(O(n^3)\) 加上些乱搞，期望得分 70pts，期望总分 210+pts，时间还剩 30s。

最后 30s 发现 T1 代码忘记写 freopen，赶紧加上。

结果

T1 还是被卡飞了，T2是错解，被汪总 hack 掉了，T3 怎么爆零了（又没写文件）？

提升

  1. 心态还有策略今天有很大提升，少了无用思考，并且在代码调不出来的情况下果断跳题，因为在平时就发现了我如果长时间调代码会头晕。

题目

T1

题目大意

在 \(n\times m\) 的网格中，从起点走到终点，每步向上下左右移动一格。进入格子 \((i,j)\) 后，价值更新为 \(b'=(b+a_{i,j})^2\bmod p\)。初始价值为 \(w\)，起点不额外结算价值，要求到达终点时价值恰好为 \(q\)。求不超过 \(16\) 步的最短路，不存在则输出 \(-1\)。

\(T\le 5,\ n,m\le 100,\ p\le 10^7\)，\(p\) 为质数，每组读入地图与起终点。

解题思路

正常用 dfs 爆搜复杂度是 \(O(4^{16})\)，剪枝是过不去的，考虑使用 meet-in-middle，先反向跑，然后用 map 计入状态，再正向跑一遍。但是反向跑的状态数可能很多，因为每个点的状态其实是 \((i,j,val)\)，对于一个点 \((x,y,val)\)，它由周围 \((x\pm 1,y\pm 1,\sqrt{val}-a_{x,y})\) 转移过来。

不过我们有一个结论：对于任意 \(a\)，满足 \(x^2 \equiv a \pmod p\) 的 \(x\) 不超过 2 个。

对于 \(x \in [1, \frac{p-1}{2}]\)，有 \(x^2 \equiv (p - x)^2 \pmod p\)

所以对于 \(a \in [1, p]\)，存在 \(x\) 满足 \(x^2 \equiv a \pmod p\)，则 \((p - x)\) 也是一个解。那么要想解的个数不超过 2 个，就必须有： \(\forall x \in [1, \frac{p-1}{2}], x^2\) 两两不同。

考虑反证。 若存在 \(a, b \in [1, \frac{p-1}{2}]\)，\(a \neq b\)，\(a^2 = b^2 \pmod p\)，则有 \(a^2 - b^2 \equiv 0 \pmod p\)

\[p\text{为素数} \Rightarrow p|(a-b)(a+b) \Rightarrow p|(a-b) \text{ or } p|(a+b) \]

由 \(a, b\) 的取值范围易知无解，故 \(x^2\) 两两不同。

知道这个结论之后，说明反过来跑的时候每个点最多由两种状态转移过来，所以这就保证了反向跑的复杂度是 \(O(2^{16})\)。

启发：

  1. 要练一练 meet-in-middle。

  2. 需要积累二次剩余相关结论（需要保证 \(p\) 是质数，因为在证明 \(a^2-b^2\equiv 0\pmod p\) 的时候需要保证 \(p\) 不是 \((a+b)(a-b)\) 的因数）：

    • \(\forall x \in [1, \frac{p-1}{2}], x^2\) 两两不同。

    • \(\forall x\in [1,p]\)，\(x\) 是完全平方数的概率是 \(1\over 2\)。其实就是在 \([1,p]\) 有 \(p-1\over 2\) 个数是完全平方数。这是因为对于每个完全平方数 \(x\) 它最多只有 2 个根，并且\(\forall x \in [1, \frac{p-1}{2}], x^2\) 两两不同。