ARC 135

前三题和后三题的 gap 有点大（

A,B,C 比较没意思。

D - Add to Square

给定一个 \(n\times m\) 的矩阵，每次可以将 \(2\times 2\) 的子矩阵共同加上一个值 \(x\)，最小化矩阵所有元素绝对值的和。

令 \(A_{i,j}\gets A_{i,j}\times (-1)^{i+j}\)，发现无论如果变化，\(A\) 每一行、每一列的和均和原矩阵相等。

实际上这就是能变换到的矩阵的充要了，必要性已经证明，充分性可以考虑根据这个方法可以构造出所有需要的矩阵。

然后就是找每一行的和为给定值，每一列的和为给定值的最小绝对值矩阵。

不妨从全 \(0\) 元素开始构造，每次给 \(A_{i,j}\) 加上 \(v\) 相当于给 \(x_i,y_j\) 加上 \(v\)，求的是 \(v\) 的最小值。

实际就是个匹配问题，若有 \(x,y\) 同正 / 同负就直接匹配相减，否则直接与 \(1\) 匹配，这样就能确定每个位置的值了。

这个贪心显然也满足的最小化的要求，最后取反的位要取回来，这个步骤不影响绝对值的和。

#include
typedef long long LL;
#define rep(i, s, t) for(int i = (s); i <= (t); i ++)
#define per(i, s, t) for(int i = (s); i >= (t); i --)
#define Ede(i, u) for(int i = head[u]; i; i = e[i].nxt)
using namespace std;

int read() {
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

const int N = 510;
int n, m, a[N][N];
LL ans, x[N], y[N], b[N][N];

void Flip(int i, int j, LL v) {
	x[i] -= v, y[j] -= v;
	b[i][j] += v;
	ans += (v > 0 ? v : - v);
}

int main() {
	n = read(), m = read();
	rep(i, 1, n) rep(j, 1, m)
		a[i][j] = read() * (((i + j) & 1) ? - 1 : 1), 
		x[i] += a[i][j], y[j] += a[i][j];
	rep(i, 1, n) rep(j, 1, m) {
		if(x[i] > 0 && y[j] > 0) Flip(i, j, min(x[i], y[j]));
		if(x[i] < 0 && y[j] < 0) Flip(i, j, max(x[i], y[j]));
	}
	rep(i, 1, n) if(x[i]) Flip(i, 1, x[i]);
	rep(j, 1, m) if(y[j]) Flip(1, j, y[j]);
	printf("%lld\n", ans);
	rep(i, 1, n) {
		rep(j, 1, m)
			printf("%lld ", b[i][j] * (((i + j) & 1) ? - 1 : 1));
		puts("");
	}
	return 0;
}

E - Sequence of Multiples

给定 \(A_1=X\)，对于 \(A_i,i\geq 2\)，均满足 \(A_{i}>A_{i-1}\) 且 \(A_i\) 为 \(i\) 的倍数。

求该长度为 \(n\) 的序列的最小和。

比 D 要可做些。显然有：

\[\displaystyle A_{i}=(\lfloor\frac{A_{i-1}}{i}\rfloor+1)\times i \]

后面的 \(\times i\) 很难看，再设 \(B_i=A_i/i\)，那么有：

\[\displaystyle B_{i}=\lfloor\frac{B_{i-1}\times (i-1)}{i}\rfloor+1 \]

即：

\[\displaystyle B_{i}=B_{i-1}-\lceil\frac{B_{i-1}}{i}\rceil+1 \]

然后，对 \(B\) 打个表，发现 \(B\) 的减小速度很快，而且后面很长一段都相等。

试着分析一下，当 \(B_{i-1}\leq i\) 时，之后的 \(B\) 显然将全都相等，而这个界限大概能在 \(O(\sqrt N)\) 处取到。

可惜不够优秀，再观察，发现 \(B\) 的一段一段是等差数列，最后一段的公差为 \(0\)。

而等差数列每一段可以快速计算，每次固定左端点找右端点只需要二分，而不同公差的段数可以证明是 \(O(n^{1/3})\) 的。

VP 的时候想到 \(\sqrt N\) 就没思路了，实际上再抱着乱搞精神看两下表也就出来了吧（

#include
typedef long long LL;
#define rep(i, s, t) for(int i = (s); i <= (t); i ++)
#define per(i, s, t) for(int i = (s); i >= (t); i --)
#define Ede(i, u) for(int i = head[u]; i; i = e[i].nxt)
using namespace std;

LL read() {
	LL x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

const LL P = 998244353;
const LL inv2 = (P + 1) / 2;
const LL inv6 = (P + 1) / 6;

LL sum1(LL l, LL r) {
	l %= P, r %= P;
	return ((l + r) * (r - l + 1) % P * inv2 % P + P) % P;
}
LL sum2(LL l, LL r) {
	l %= P, r %= P;
	LL s1 = (r * (r + 1) % P * (2 * r % P + 1) % P + P) % P;
	LL s2 = ((l - 1) * l % P * (2 * l % P - 1) % P + P) % P;
	return ((s1 - s2 + P) % P) * inv6 % P;
}

int main() {
	int T = read();
	while(T --) {
		LL n = read(), x = read();
		LL B = x, ans = 0;
		for(LL l = 1, r; l <= n; l = r + 1) {
			LL D = (B + 1 - (B + l) / (l + 1)) - B;
			LL L = l, R = n;
			if(D) R = min(n, l + B / (- D));
			while(L < R) {
				LL mid = (L + R + 1) >> 1;
				LL cur = B + D * (mid - l);
				LL las = B + D * (mid - l - 1);
				if((__int128) cur * mid > (__int128) las * (mid - 1)) L = mid; else R = mid - 1;
			}
			r = L;
			ans = (ans + (((B % P) - (D % P) * (l % P) % P + P) % P) * sum1(l, r) % P + (D % P) * sum2(l, r) % P) % P;
			B += D * (r - l);
			B = B + 1 - (B + r) / (r + 1);
		}
		printf("%lld\n", (ans % P + P) % P);
	}
}

F 照例是不会的（