很牛的题。这边默认你啥也不会。
手玩或看题解之后发现答案好像只和初末状态有关，即任意一个方案都能得到对应的结果。我们直接猜这个是对的。
这东西怎么证明呢？物理中，有一个东西叫重力势能，其大小为 \(E = mgh\)，一个物体无论怎么运动，其势能之差 \(E_1 - E_2\) 都为 \(mg\Delta h\)，这和需要证明的结论类似。我们给出一个证明的方法：假设操作了 \(i\) 次后棋盘的状态为 \(S_i\)，特别地，初始棋盘状态为 \(S_0\)，最后一次操作后的棋盘状态为 \(S_k\)。如果我们可以设计出一个函数 \(F(S)\)，即当前状态 \(S\) 到一个整数的映射，且满足 \(F(S_i) - F(S_{i + 1})\) 第 \(i\) 次操作增加的魔力值。那么我们就可以发现产生的总魔力值为 \((F(S_0) - F(S_1)) + (F(S_1) - F(S_2)) + (F(S_2) - F(S_3)) + \dots (F(S_{k - 1}) - F(S_k)) = F(S_0) - F(S_k)\)。这就只和终末状态有关了，正如 \(\Delta E = mg\Delta h\) 一样！也就是说，如果我们能找到一个这样的函数 \(F(S)\)，那么就得到了证明。同时，如果我们设计出 \(F(S)\)，那么我们也可以得到本题的答案。我们称 \(F(S)\) 为当前状态的势能。
如何构造呢，首先一整个状态太麻烦了，我们考虑 \(a_{x, y} \times f(x, y)\) 表示 \((x, y)\) 上星的势能，则 \(F = \sum a_{x, y} \times f(x, y)\)，又因为 \(x, y\) 独立，可以把 \(f(x, y)\) 改为 \(f(x) + f(y)\)。
对于 \(f(x)\)，如果移动 \(x_1, x_2\) 两颗星星，\(x_1 < x_2\)，则根据定义，\(f(x_1) + f(x_2) - f(x_1 + 1) - f(x_2 - 1) = x_2 - x_1 - 1\)，即 \(f(x_1 + 1) - f(x_1) - x_1 = f(x_2) - f(x_2 - 1) - x_2 - 1\)，令 \(t = x_2 - 1\)，则 \(f(x_1 + 1) - f(x_1) - x_1 = f(t + 1) - f(t) - t\)，由于对于所有 \(x1 < x2\) 都满足这个式子，所以 \(f(x) - f(x - 1) - x\) 为定值，且我们只要知道这个定值和 \(f(0)\) 就能知道所有 \(f(x)\) 了，不妨设这个定值和 \(f(0)\) 都为 \(0\)，那么 \(f(x) = f(x - 1) + x\)，显然 \(f(x) = \frac{x^2 + x}{2}\)。对于 \(y\) 是同理的，于是这道题就做完了。时间复杂度 \(\mathcal{O}(nm)\)。
::::success[code]
include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 2e2 + 10, mod = 998244353;
template
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {
cout << arg << ' ';
dbg(args...);
}
namespace Loop1st {
int n, m, a[N][N];
ll ans = 0;
void main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
ans += (ll)a[i][j] * (i * (i + 1) / 2 + j * (j + 1) / 2);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
ans -= (ll)a[i][j] * (i * (i + 1) / 2 + j * (j + 1) / 2);
}
}
cout << ans << '\n';
}
}
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while (T--) Loop1st::main();
return 0;
}
// start coding at 16:24
// finish debugging at 16:27
::::
总结一下，势能函数和答案只和初末状态有关是互为因果的，下次如果见到只和初末状态有关的题，可以考虑构造势能函数解决。