题解 矩阵游戏
题意简述
给定 ((n-1) imes (m-1)) 的矩阵 (b) ，构造 (n imes m) 的矩阵 (a) 满足：
并且满足 (a_{i,j}in [0,10^6]) ，需要判无解，多组数据。
(1le Tle 10,2le n,mle 300,0le b_{i,j}le 4 imes 10^6) 。
部分分表格：
| 测试点编号 | $n,mle $ | 特殊限制 |
|---|---|---|
| (1sim 4) | (3) | 无 |
| (5sim 7) | (10) | (m=2) |
| (8sim 10) | (100) | (m=2) |
| (11sim 15) | (300) | (0le b_{i,j}le 1) |
| (16sim 20) | (300) | 无 |
题目分析
测试点 (1sim 4)
测试点 (5sim 7)
(m=2) ，不妨设 (c_j=a_{j,1}+a_{j,2}) ，那么 (b_{j,1}=c_j+c_{j+1}) 并且有 (c_jin [0,2 imes 10^6]) ，暴力枚举 (c_n) 就可以一遍 (mathcal O(n)) 推出 (c_{1sim n-1}) ，然后直接检查即可，时间复杂度 (mathcal O(2 imes 10^6 imes Tn)) 。
测试点 (8sim 10)
一样的，设 (c_j=a_{j,1}+a_{j,2}) ，可以得出 (c_j=sumlimits_{k=j}^{n-1}(-1)^{k-j}b_{k,1}+(-1)^{n-j}c_n) ，对于每个 (1le j<n) ，由 (c_jin [0,2 imes 10^6]) 可以推出其对于 (c_n) 的限制，然后就可以做了，时间复杂度 (mathcal O(Tn)) 。
测试点 (11sim 15)
只会一个和满分做法差不多的做法。
此时 (a_{i,j}in [0,1]) ，想到 2-SAT 。
令 (c_{i,j}=sumlimits_{s=i}^{n-1}sumlimits_{t=j}^{m-1}(-1)^{n-s+m-t}b_{s,t}) ，那么就会有 (a_{i,j}=(-1)^{n-i+m-j}c_{i,j}+(-1)^{n-i}a_{i,m}+(-1)^{m-j}a_{n,j}-a_{n,m}) ，又由于 (0le a_{i,j}le 10^6) ，那么 (a_{i,j}) 就相当于给了一个限制条件：
暴力枚举 (a_{n,m}) ，那么限制的就只有两个变量，看每个变量取 (0) 或 (1) 的时候对另一个变量的限制，然后跑 2-SAT 即可。
时间复杂度 (mathcal O(Tnm)) 。
测试点 (16sim 20)
显然如果第 (n) 行和第 (m) 列的 (a) 的取值都确定了，那么所有的 (a) 的取值都可以通过 (b) 唯一确定。根据经验或者大胆猜想， (a_{i,j}) 的取值肯定可以表示为某一个固定的数 (c_{i,j}) 和 (a_{i,m},a_{n,j},a_{n,m}) 的线性表示。
令 (c_{i,j}=sumlimits_{s=i}^{n-1}sumlimits_{t=j}^{m-1}(-1)^{n-s+m-t}b_{s,t}) ，那么就会有 (a_{i,j}=(-1)^{n-i+m-j}c_{i,j}+(-1)^{n-i}a_{i,m}+(-1)^{m-j}a_{n,j}-a_{n,m}) ，又由于 (0le a_{i,j}le 10^6) ，那么 (a_{i,j}) 就相当于给了一个限制条件：
不等关系不难想到差分约束，但是注意到这个限制条件中有三个变量 (a_{i,m},a_{n,j},a_{n,m}) ，而差分约束模型只能限制两个变量间的关系，不过没有关系，我们可以“换元”，令 (S_i=(-1)^{n-i}a_{i,m},T_j=a_{n,m}-(-1)^{m-j}a_{n,j}) ，那么这个限制条件也可以写成：
于是就转化成经典差分约束模型了，完全图直接使用 bellmanford 就行了，时间复杂度 (mathcal O(Tnm(n+m))) ，有一点点卡常。