[AGC063C] Add Mod Operations

· · 题解

或许更好的阅读体验。

思路：

先考虑什么情况无解；其实只有相同的 a 对应不同的 b 时无解，于是先把 a 相同的缩一块。

然后把 a 从小到大排序得到 a'，注意到我们可以选择 x 和 a'_n + x，这样造成的影响是将 a'_n \gets 0 然后扔到 a'_1 去，a'_{1 \sim n - 1} 全部加 x 且右移一位。

那么这样操作 n - 1 次后，显然得到的序列是 [0, x_n, x_n + x_{n - 1}, \cdots, \sum_{i = 2}^{n - 1}x_i, a'_1 + \sum_{i = 1}^{n - 1}x_i]（设 id_i 表示这个序列第 i 位实际上是由原来的 a_{id_i} 得到的）。

你发现这样得到的前面 n - 1 个是单增的，但是我们最终目标 b 不是单增的，怎么办呢？相当于限制了 b 排序后下标和上面序列的 id 相同（注意要忽略 id_n，因为它不是单增的）。

考虑钦定一个 p = 3 \cdot 10^9，我们给每个 b_i 不断增加 p 直到所有 b' 是按照 id 排序的，最后直接模 p 就行；然后最后一步操作考虑 b'_{id_1} 和 p。

则序列会变成 [b_{id_1}, (x_n + b'_{id_1}) \bmod {p}, \cdots, (\sum_{i = 2}^{n - 1} x_i) \bmod p, (a'_1 + \sum_{i = 1}^{n - 1}x_i + b'_{id_1}) \bmod p]；相当于我们有限制：

\sum_{i = n - k + 1}^{n - 1} x_i + b'_{id_1} = b'_{id_k}

于是想到钦定 x_{n - i + 1} = b'_{id_i} - b'_{id_{i - 1}}。

但是对于最后那个 a'_1 + \sum_{i = 1}^{n - 1}x_i + b'_{id_1} = a'_1 + x_1 + b'_{id_{n - 1}} = b_{id'_n}，于是钦定 x_1 = b_{id'_n} - b'_{id_{n - 1}} - a_1' 即可，因为 x_1 \ge 0，于是要满足 b'_{id_n} - b'_{id_{n - 1}} \ge a_1'，调整 b'_{id_n} 一直加 p 即可。

于是这样可以在 n 次操作中构建出来。时间复杂度为 O(n^2)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
const ll mod = 2e9, lim = 1e18;
inline ll read(){
    ll 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 << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
} 
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
struct Node{
    ll a, b;
    inline bool operator<(const Node&rhs)const{
        return a < rhs.a;
    }
}A[N];
int n, cnt;
ll x[N], y[N];
int main(){
    n = read();
    for(int i = 1; i <= n; ++i)
      A[i].a = read();
    for(int i = 1; i <= n; ++i)
      A[i].b = read();
    sort(A + 1, A + n + 1);
    A[0].a = -1; // !!!!
    for(int i = 1; i <= n; ++i){
        if(A[i].a == A[cnt].a){
            if(A[i].b != A[cnt].b){
                puts("No");
                return 0;
            }
        }
        else
          A[++cnt] = A[i];
    }
    puts("Yes");
    write(n = cnt);
    putchar('\n');
    reverse(A + 1, A + n + 1);
    reverse(A + 1, A + n);
    for(int i = 2; i < n; ++i){
        while(A[i].b < A[i - 1].b)
          A[i].b += mod;
    }
    x[n] = A[1].b, y[n] = mod;
    for(int i = 2; i < n; ++i)
      x[n - i + 1] = A[i].b - A[i - 1].b;
    while(A[n].b - A[n - 1].b < A[n].a)
      A[n].b += mod;
    x[1] = A[n].b - A[n - 1].b - A[n].a;
        // for(int j = 1; j <= n; ++j){
        //     // A[j].a = (A[j].a + x[i]) % y[i];
        //     cerr << A[j].a << ' ' << A[j].b << '\n';
        // }
        // cerr << '\n';
    for(int i = 1; i <= n; ++i){
        if(i < n)
          y[i] = x[i] + A[n - i].a;
        // assert(x[i] <= lim && y[i] <= lim && x[i] < y[i] && x[i] >= 0);
        write(x[i]);
        putchar(' ');
        write(y[i]);
        putchar('\n');
        for(int j = 1; j <= n; ++j){
            A[j].a = (A[j].a + x[i]) % y[i];
            // cerr << A[j].a << ' ';
        }
        // cerr << '\n';
    }
    // for(int j = 1; j <= n; ++j)
    //   assert(A[j].a == (A[j].b % mod));
    return 0;
}