https://codeforces.com/contest/2055/problem/C
题目大意
题目给出一个 $n \times m \ ( 2 \le n, m \le 1000 )$ 的矩阵，给出一条起点为 $(0, 0)$ 终点为 $(n - 1, m - 1)$ 的由向右向下走出的路径。这条路径由 $n + m - 2$ 个字母 $DR$ 构成的串组成。$D$ 表示向下，$R$ 表示向右。题目给出的矩阵是从某原矩阵 $A$ 将这条路径上的所有元素设置为 $0$ 的矩阵。原矩阵 $A$ 符合，所有行和所有列的和都是某相同的定值。题目总有解存在，请输出某个成立的原矩阵 $A$。
简要题解
题目看起来像个解方程的题，但是这个数据量高斯消元复杂度肯定炸了。
观察：
- 如果知道行或列的和 $x$ 则我们可以直接确定 $a[0][0]$ 的值，因为从 $(0, 0)$ 出发，如果向右走，则下侧的数字都是已知数，如果向下走，则右侧的数字都是已知数。
- 进一步，如果我们填出了 $(0, 0)$ 则我们可以继续按照顺序唯一的确定数。如果要填 $(i, j)$ 则子矩阵 $(0, 0) \sim (i, j)$ 除了 $(i, j)$ 肯定都是填好的，也就是说这其实和 $0, 0$ 的情况完全一致了，可以由下一步的方向，直接根据已经完全填好的行列填出 $i, j$ 的值。
- 注意到对于 $n \neq m$ 的情况，由于 $xn = xm$ 则 $x$ 只能为 $0$。
注意到最后一格需要同时满足行和列。而题目告诉我们这总是有解的，于是我们可以直接设第一格填 $b$ 于是我们可以推导出最后一格需要同时满足行列的等式。但这个方法证明起来非常麻烦。下述代码通过了题目，但是细节十分难解释为什么成立。
void solve() {
int n, m; cin >> n >> m;
string path; cin >> path;
vector<vector<LL>> a(n, vector<LL>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
int x = 0, y = 0;
LL tara = 0; // tarb = 1
if (path[0] == 'R') {
for (int i = 1; i < n; i++) {
tara += a[i][0];
}
y++;
} else { // path[0] == 'D'
for (int i = 1; i < m; i++) {
tara += a[0][i];
}
x++;
}
vector<vector<LL>> b(n, vector<LL>(m));
b[0][0] = 1;
for (int i = 1; i < n + m - 2; i++) {
LL suma = 0, sumb = 0;
if (path[i] == 'R') {
for (int i = 0; i < n; i++) {
suma += a[i][y];
sumb += b[i][y];
}
a[x][y] = tara - suma;
b[x][y] = 1 - sumb;
y++;
} else { // path[i] == 'D'
for (int i = 0; i < m; i++) {
suma += a[x][i];
sumb += b[x][i];
}
a[x][y] = tara - suma;
b[x][y] = 1 - sumb;
x++;
}
}
LL suma = 0, sumb = 0;
for (int i = 0; i < n; i++) {
suma += a[i][m - 1];
sumb += b[i][m - 1];
}
a[n - 1][m - 1] = tara - suma;
b[n - 1][m - 1] = 1 - sumb;
for (int i = 0; i < m - 1; i++) {
suma -= a[n - 1][i];
sumb -= b[n - 1][i];
}
// cerr << suma << ' ' << sumb << endl;
LL val = sumb ? -suma / sumb : 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << (a[i][j] + b[i][j] * val) << (" \n"[j == m - 1]);
}
}
}
实际上对于 $n = m$ 的情况，任意的和 $s$ 都是成立的。
考虑上 $n - 1$ 行，和左 $n - 1$ 列，由于 $(0, 0) \sim (n - 2, n - 2)$ 这个区域是同时被这两种选法共用的，则我们可以得出 $(n - 1, 0) \sim (n - 1, n - 2)$ 的和与 $(0, n - 1) \sim (n - 2, n - 1)$ 的和是一致的，又由行列的和都是一样的，因此得出确实最后一行，最后一列需要的 $a[n - 1][n - 1]$ 是同一个值。
复杂度
$T$：$O(nm)$
$S$：$O(nm)$
代码实现
下面代码里其实 tar 对于 $n = m$ 的情况设置成任何值都行。所以也可以对所有情况总是设置成 $0$。
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, m; cin >> n >> m;
string path; cin >> path;
vector<vector<LL>> a(n, vector<LL>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
int x = 0, y = 0;
// target can always be 0!
LL tar = (n == m ? 0 : 0);
LL sum = 0;
if (path[0] == 'R') {
for (int i = 1; i < n; i++) {
sum += a[i][0];
}
y++;
} else { // path[0] == 'D'
for (int i = 1; i < m; i++) {
sum += a[0][i];
}
x++;
}
a[0][0] = tar - sum;
for (int i = 1; i < n + m - 2; i++) {
sum = 0;
if (path[i] == 'R') {
for (int i = 0; i < n; i++) {
sum += a[i][y];
}
a[x][y] = tar - sum;
y++;
} else { // path[i] == 'D'
for (int i = 0; i < m; i++) {
sum += a[x][i];
}
a[x][y] = tar - sum;
x++;
}
}
sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i][m - 1];
}
a[n - 1][m - 1] = tar - sum;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << a[i][j] << (" \n"[j == m - 1]);
}
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. Scarecrow - Codeforces Round 996 (Div. 2)