题解：CF2032E Balanced

· · 题解

不会性质，只能硬算了。

Solution

注意到如果 n 个数能变为 x，那么一定能变 x+4，因为可以在 n 个数上各进行一次操作，故 n 个数如果能变得相同，那么需要能变成 x,x+1,x+2,x+3 中的一个，x 是一个巨大的数，取到 10^{17} 即可，问题转化为检查可行性。

设 n 个数分别进行了 b_1,b_2,...,b_n 次操作，则 n 个数会变为 a_1+2b_1+b_2+b_n,a_2+2b_2+b_1+b_3,...,a_n+2b_n+b_{n-1}+b_1。

考虑高斯消元，这个东西是 n 个变量和 n 个条件，且条件线性不相关，故对于每次检查，只有唯一一组 b 可以满足条件，那么直接设矩阵消元求方程组即可，然而有三个问题，下面分别来考虑如何解决。

细节

由于消元可能出负数，将所有 b 加上一个大偏移量即可。

时间复杂度

直接消元复杂度 O(n^3)，显然不可做，但矩阵长成如下的样子。

\begin{pmatrix}2&1&&&\cdots&&1\\1&2&1\\&1&2&1\\&&&&\ddots\\1&&&&&1&2\end{pmatrix}

模拟一下过程不难发现每行最多有三个元素，且每行最多对两行进行消元，故消元复杂度可以降至 O(n)。

精度

直接用 double 做大概率是无法通过的，考虑对一个大模数做这件事，这个模数要是质数，因为要求逆元，质数更为好做，我选的模数是 99999999999999997 ，模数比较小会被卡。

如果存在答案，猜测它不会太大，最多就 10^{18}，然后直接算，最后在模拟检验一下就好。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int b[200010],c[200010],d[200010],e[200010],n,a[200010],inv[200010];
const int mod=99999999999999997;
int q_pow(int x,int y){
    if(!y) return 1;
    int z=q_pow(x,y>>1);
    if(y&1) return (__int128)z*z%mod*x%mod;
    else return (__int128)z*z%mod;
}
bool check(int x){
    for(int i=1;i<=n;i++) b[i]=x-a[i];
    c[1]=1;
    c[n-1]=1;
    c[n]=2;
    d[1]=1;
    d[n-1]=1;
    for(int i=1;i<=n;i++) e[i]=2;
    for(int i=1;i<n-1;i++){
        int x=q_pow(e[i],mod-2);
        inv[i]=x;
        b[n]=(b[n]-(__int128)b[i]*c[i]%mod*x%mod+mod)%mod;
        c[i+1]=(c[i+1]-(__int128)c[i]*x%mod+mod)%mod;
        c[n]=(c[n]-(__int128)c[i]*x%mod*d[i]%mod+mod)%mod;
        c[i]=0;
        b[i+1]=(b[i+1]-(__int128)b[i]*x%mod+mod)%mod;
        e[i+1]=(e[i+1]-x+mod)%mod;
        d[i+1]=(d[i+1]-(__int128)x*d[i]%mod+mod)%mod;
    }
    int y=q_pow(e[n-1],mod-2);
    inv[n-1]=y;
    b[n]=(b[n]-(__int128)c[n-1]*y%mod*b[n-1]%mod+mod)%mod;
    c[n]=(c[n]-(__int128)d[n-1]*c[n-1]%mod*y%mod+mod)%mod;
    b[n]=(__int128)b[n]*q_pow(c[n],mod-2)%mod;
    for(int i=1;i<n;i++) b[i]=(b[i]-(__int128)b[n]*d[i]%mod+mod)%mod,d[i]=0;
    for(int i=n-1;i>1;i--){
        b[i]=(__int128)b[i]*inv[i]%mod;
        b[i-1]=(b[i-1]-b[i]+mod)%mod;
    }
    b[1]=(__int128)b[1]*inv[1]%mod;
    e[1]=1;
    for(int i=1;i<=n;i++) b[i]=(b[i]+10000000000000000)%mod;
    b[n+1]=b[1];
    for(int i=2;i<=n;i++) if(a[i]+2*b[i]+b[i+1]+b[i-1]!=a[1]+2*b[1]+b[2]+b[n]) return 0;
    for(int i=1;i<=n;i++) cout<<b[i]<<' ';
    cout<<'\n';
    return 1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        int f=1;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        if(n==1){
            cout<<0<<endl;
            continue;
        }
        for(int i=0;i<=3;i++){
            if(check(1e17+i)){
                f=0;
                break;
            }
        }
        if(f) cout<<-1<<'\n';
    }
    return 0;
}