[AGC063C] Add Mod Operations 题解

题目链接

点击打开链接

题目解法

好难想的构造题！！！到底是怎么想到的？？？

首先无解的条件是好判的，如果有 \(i\neq j,\;a_i=a_j\) 且 \(b_i\neq b_j\)，那么就无解

将 \(a\) 从小到大排序
考虑下面的构造方式：\(y=curmax+x\)，这样可以使最大值清 \(0\)，其他数都 \(+x\)，这是一个类似消元的过程，每次可以消去 \(a_{max}\)
不难发现，\(n-1\) 次后，序列将变成：\(a_1+\sum\limits_{i=1}^{n-1}x_i,0,x_{n-1},x_{n-1}+x_{n-2},...,\sum\limits_{i=2}^{n-1}a_i\)
考虑构造合适的 \(x_i\;(i\in[1,n-1])\)，使 \(n-1\) 次之后 \(a_i=b_i-b_2\)
可以使：\(x_1=-a_1+b_1-b_n,\;x_i(i\in[2,n-1])=b_{n-i+2}-b_{n-i+1},\;x_n=b_2\)
但这样 \(x_i\) 可能 \(<0\)，直接让 \(x_i+inf\to x_i\) 即可

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

#include <bits/stdc++.h>
#define int long long
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=1100,inf=1e10;
int n,x[N],y[N];
pii v[N];
signed main(){
    n=read();
    F(i,1,n) v[i].x=read();
    F(i,1,n) v[i].y=read();
    sort(v+1,v+n+1);
    int cur=0;
    F(i,1,n){
        int j=i;
        while(j<n&&v[j+1].x==v[i].x) j++;
        bool flg=1;
        F(k,i+1,j) if(v[k].y!=v[k-1].y){ flg=0;break;}
        if(!flg){ puts("No");exit(0);}
        v[++cur]=v[i],i=j;
    }
    n=cur;
    if(n==1){ puts("Yes");puts("1");printf("%lld %lld\n",(v[1].y-v[1].x+inf)%inf,inf);exit(0);}
    x[1]=-v[1].x+v[1].y-v[n].y+inf;
    F(i,2,n-1) x[i]=v[n-i+2].y-v[n-i+1].y+inf;
    x[n]=v[2].y;
    F(i,1,n-1){
        y[i]=v[n-i+1].x+x[i];
        F(j,1,n) v[j].x=(v[j].x+x[i])%y[i];
    }
    y[n]=inf;
    F(j,1,n) v[j].x=(v[j].x+x[n])%y[n];
    puts("Yes");printf("%d\n",n);
    F(i,1,n) printf("%lld %lld\n",x[i],y[i]);
    fprintf(stderr,"%d ms\n",int64_t(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}