代码源每日一题 div1 #807 矩阵操作

题意

给你一个二维矩阵，每次可以对一行或者一列加1（modk），问，最少需要多少次操作，能让整个矩阵变成全0。

思路

首先，我们先考虑对每行/列加这个操作，很容易想到，用 $r_i$ 表示给第i行加的次数， $c_i$ 表示给第i列加了多少次。那么，我们需要求一个约束条件为 $r_i+c_i+a_{ij}=0(modk)$ ， $\sum(r_i+c_i)$ 的最小正整数解。

先考虑什么情况下有解，稍微观察下可以发现： $r_i和c_i$ 总共有n+m个未知数，而方程有 $n ? m$ 个

这就提示我们，里面有很多方程都是线性相关的，也就是说，我们可以消除掉一些方程！

现在尝试一下消除，我们不妨假设 $r_1$ 是已知的，那么 $c_j=-r_1-a_{1j}(modk)$ 。这样我们便求出了所有的 $c_j$ 。可以得出 $c_1=-r_1-a_{11}(modk)$

因为c1已经求出来了，我们可以求出所有的 $r_i$ ，与上面类似 $r_i=-c_1-a_{i1} (modk)=r_1+a_{11}-a_{i1}$ 。

把 $r_i$ 和 $c_i$ 代入 $r_i+c_i+a_{ij}=0(modk)$ ，可以发现 $r_1$ 可以消掉！得到 $a_{11}-a_{i1}-a_{1j}+a_{ij}=0(modk)$ ，所以只要对于所有的数字检验一下这个等式的成立性，就可以求出是否有解了。

那么继续考虑第二个问题，怎么求一个最优解 $\sum(r_i+c_i)$ ？

先来个结论， $r_i$ 或者 $c_i$ 里面必定有一个为0。

证明：假设最优解中， $r_i$ 和 $c_i$ 全都不为0。

$n > = m$ , 可以对所有的 $r_i-1，c_i+1$ ，那么整个矩阵的 $a_{ij}$ 都不变，而且操作次数减少了 $n ? m > = 0$ 次。会使得结果不会变差，甚至变得更好
$n < m$ , 可以对所有的 $r_i+1，c_i-1$ ，那么整个矩阵的 $a_{ij}$ 都不变，而且操作次数减少了 $m ? n > 0$ 次。会使得结果变好。

我们可以做上面两种操作，直到 $c_i, r_i$ 有一个为0，并且解更优。矛盾！所以结论得证。

那么有一个为0有什么用呢？

我们不妨假设有一个 $r_i$ 为0，根据等式 $r_i+c_i+a_{ij}=0(modk)$ ，我们可以求出所有的 $c_i$ ，再代入一次进而再求出所有的 $r_i$ ，这样就可以求出一个解了。

列的做法同理，我们的做法就是，暴力枚举哪一行/列的操作次数为0即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10, M = 2 * N;  
typedef long long LL;
typedef pair<int,int> PII;
using tp = tuple<int,int,int>;
bool multi = false;

int n, m, k;
int a[N][N];
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x;
}
int mod(int x, int y = k) {
    return (x % y + y) % y;
}
bool check() {

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++)
            if(mod(a[1][1] - a[1][j] - a[i][1] + a[i][j]) != 0) return false;
    }
    return true;
}

//第x行不发生变化, 那么可以算出c1, 再算出所有的ri
LL cal1(int x) {
    int c1 = mod(-a[x][1]);
    LL res = 0;
    for(int i = 1; i <= n; i++) res += mod(-a[i][1] - c1);
    for(int i = 1; i <= m; i++) res += mod(-a[x][i]);
    return res;
}

//第x列不发生变化, 那么可以算出r1, 再算出所有的ci
LL cal2(int x) {
    int r1 = mod(-a[1][x]);
    LL res = 0;
    for(int i = 1; i <= n; i++) res += mod(-a[i][x]);
    for(int i = 1; i <= m; i++) res += mod(-r1 - a[1][i]);
    return res;
}

void solve() {
    n = read(), m = read(), k = read();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) a[i][j] = read();
    
    if(!check()) {
        puts("-1");
        return;
    }
    
    LL res = 1e18;
    for(int i = 1; i <= n; i++) res = min(res, cal1(i));
    for(int i = 1; i <= m; i++) res = min(res, cal2(i));
    cout << res << endl;
}   

int main()
{
#ifdef ONLINE_JUDGE
#else 
    freopen("I.txt", "r", stdin);
#endif
    int T = 1;
    if(multi) cin >> T;
    while(T--) solve();
    return 0;
}