AT_agc064_e [AGC064E] Cross Sum Construction题解

Y204335 · 2024-11-09 18:22:05 · 题解

[AGC064E] Cross Sum Construction

题目大意

给定 n 和长度为 n 的序列 A,B，令可重集 X=\left\{a+b| a\in A,b\in B\right\}，要求构造 n\times n 的矩阵 M，令可重集 S=\left\{\sum_{i=1}^{n}M_{x,i}+\sum_{i=1}^{n}M_{i,y}-M_{x,y}|1\le x,y\le n\right\}，使得 \sum_{i}\min\left(sum_{i\in X},sum_{i\in S}\right) 最大（注意 sum_{i\in X} 指 i 在 X 中出现的次数）。

题目分析

由于 i 的贡献最大就是 i 在 X 中出现的次数，所以要让 X 中的元素尽可能在 S 中出现。令 s_{x,y}=\sum_{i=1}^{n}M_{x,i}+\sum_{i=1}^{n}M_{i,y}-M_{x,y}（也就是 M 中这一行一列的元素之和），考虑如何通过 s_{i,j} 反推 M_{i,j}。

首先，由于 M 中的每个数字都会被 2n-1 个 s 算上，所以 M 中所有元素之和 sum=\frac{\sum_{i=1}^{n}\sum_{j=1}^{n}s_{i,j}}{2n-1}，由于 sum 一定为整数，所以如果要使 S 与 X 一致，\sum_{i\in X}i\times sum_{i\in X} 一定要是 2n-1 的倍数，先考虑满足倍数关系的情况（不满足倍数关系可以通过改变其中一个 s 来处理）。

令 r_x=\sum_{i=1}^{n}s_{i,x},c_x=\sum_{i=1}^{n}s_{x,i}，则：

所以 \left(r_i+c_j\right)\left(2n-1\right)-2sum 需要是 n-1 的倍数。

• 若 \forall 1\le i,j\le n,\left(r_i+c_j\right)\left(2n-1\right)\equiv 2sum\pmod{n-1} 则：

• 若 \forall 1\le i,j\le n,r_i\equiv r_j,c_i\equiv c_j\pmod{n-1}，则：

所以 \forall 1\le i,j\le n,\left(r_i+c_j\right)\left(2n-1\right)\equiv 2sum\pmod{n-1} 与 \forall 1\le i,j\le n,r_i\equiv r_j,c_i\equiv c_j\pmod{n-1} 互为充要条件。

考虑如何使得 \forall 1\le i,j\le n,r_i\equiv r_j,c_i\equiv c_j\pmod{n-1}，可以通过构造下标使得 \forall 1\le i\le n,r_i=\sum_{i=1}^{n}A_i+B_i,c_i=\sum_{i=1}^{n}A_i+B_i，按照 n 的奇偶性分开考虑，注意以下下标从 0 开始（0\dots n-1），默认模 n。

1. 当 n\bmod 2=1 时，可以借助溢出转变下标奇偶性来处理，令 s_{i,j}=A_{-i+j}+B_{-2i+j}，此时 r_x=c_x=\sum_{i=1}^{n}A_i+B_i。

2. 当 n\bmod 2=0 时，设 s_{i,j}=A_l+B_k，先考虑 k，当 i,j 改变时，k 需要不重不漏，可以构造出 k=\begin{cases}-i+j&-i+j\ne 0\text{ 且}-i+j\ne\frac{n}{2}\\\frac{n\times\left(i\bmod2\right)}{2}&-i+j=0\text{ 或}-i+j=\frac{n}{2}\end{cases}，再考虑 l，可以发现直接通过 i,j 算出 l 是困难的，可以反过来，从 l 反推 i,j，分别从 0\sim n-1 枚举 l 和 x，令 \left(i,j\right)=\begin{cases}\left(2\times\left\lfloor\frac{l}{2}\right\rfloor+\frac{n\times\left(l\bmod2\right)}{2}+x,2\times\left\lfloor\frac{l}{2}\right\rfloor+2x\right)&x=0\sim\frac{n}{2}-1\\\left(2\times\left\lfloor\frac{l}{2}\right\rfloor+\frac{n\times\left(l\bmod2\right)}{2}+x,2\times\left\lfloor\frac{l}{2}\right\rfloor+2x+1\right)&x=\frac{n}{2}\sim n-1\end{cases}，此时 r_x=c_x=\sum_{i=1}^{n}A_i+B_i（具体证明可以看官方题解）。

这样就解决了 \left(\sum_{i\in X}i\times sum_{i\in X}\right)\bmod 2n-1=0 时的构造，当 \left(\sum_{i\in X}i\times sum_{i\in X}\right)\bmod 2n-1\ne 0 时，可以通过不断给某个 s_{i,j} 加上 n-1（这是为了在构造完后进行变化仍能满足 \forall 1\le x\le n,r_i\equiv r_x,c_j\equiv c_x\pmod{n-1}）来进行处理。

时间复杂度 O(n^2)。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 510;
int t, n;
ll s[N][N], sum, r[N], c[N], cnt[N], a[N], b[N];
void solve()
{
    cin >> n;
    sum = 0;
    for (int i = 0; i < n; i++) {
        r[i] = c[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    if (n == 1) {
        cout << a[0] + b[0] << '\n';
        return;
    }
    if (n % 2) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                s[i][j] = a[(n + j - i) % n] + b[(2 * n - 2 * i + j) % n];
            }
        }
    } else {
        for (int i = 0; i < n - 1; i++) {
            cnt[i] = -1;
        }
        for (int i = 0; i < n; i++) {
            if (cnt[(n - 1 + a[i] % (n - 1)) % (n - 1)] != -1) {
                swap(a[cnt[(n - 1 + a[i] % (n - 1)) % (n - 1)]], a[0]);
                swap(a[i], a[n / 2]);
                break;
            }
            cnt[(n - 1 + a[i] % (n - 1)) % (n - 1)] = i;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || (n + j - i) % n == n / 2) {
                    s[i][j] = a[(i % 2) * n / 2];
                } else {
                    s[i][j] = a[(n + j - i) % n];
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int x = (2 * (i / 2) + (i % 2) * n / 2 + j) % n, y = (2 * (i / 2) + 2 * j + (j >= n / 2)) % n;
                s[x][y] += b[i];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum += s[i][j];
        }
    }
    while (sum % (2 * n - 1)) {
        s[0][0] += n - 1;
        sum += n - 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            r[i] += s[i][j];
            c[j] += s[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << ((r[i] + c[j]) - 2 * sum / (2 * n - 1)) / (n - 1) - s[i][j] << ' ';
        }
        cout << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}