CF2038B Make It Equal 线性题解

· · 题解

这是一个线性做法。

设 i \to i+1 的贡献为 b_i，也就是 a_i 减去 2b_i 并让 a_{i+1} 获得 b_i 个能量。特别的，b_0 表示 n \to 1 的贡献。

设最后所有的数为 x。

\begin{cases} a_1+b_0-2b_1=x\\ a_2+b_1-2b_2=x\\ \dots\\ a_n+b_{n-1}-2b_0=x \end{cases}

先将 n 个方程相加，得到：

\sum b_i = \sum a_i - nx

也就是答案等于 \sum _{i=1}^n a_i -nx。

接下来尝试解方程组，将第 i 个方程乘上 2^{i-1}，可得：

\sum_{i=1}^n 2^{i-1} a_i -(2^n-1)b_0=(2^n-1)x

也就是

b_0+x = \frac{\sum 2^{i-1} a_i}{2^n-1}

显然不可能存下来 \sum 2^{i-1} a_i，由于 b_0+x 为整数，我们只需要知道为整数的 \frac{\sum 2^{i-1} a_i}{2^n-1}。

考虑取模，取两个大质数 M_1,M_2 > \max a_i。如果

\left(\sum 2^{i-1}a_i\right) (2^n-1) ^{M_1-2} \bmod M_1 = \left(\sum 2^{i-1}a_i\right) (2^n-1) ^{M_2-2} \bmod M_2

我们断言 \left(\sum 2^{i-1}a_i\right) (2^n-1) ^{M_1-2} \bmod M_1 即我们想求之整数 \frac{\sum 2^{i-1}a_i}{2^n-1}。（感性理解一下如果这个数为分数，有理数取余后逆元大不相同，但是我不大会证明准确率）

然后我们则有

b_0 = \frac{\sum 2^{i-1}a_i}{2^n-1} - x

记为

b_0=c_0-x

代入 a_n+b_{n-1}-2b_0=x 可以得到 b_{n-1}=2c_0-a_n -x，记为 b_{n-1} = c_{n-1}-x，依次向上代入得到 n 个方程 b_i=c_i-x。由于 b_i \ge 0，解得 x \le \min b_i。

代入 x= \min b_i 即可得答案。

复杂度线性。

放个代码：

:::info[code]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
template<typename tp> inline void cmin(tp &a,tp b){(b<a)&&(a=b);}
template<typename tp> inline void cmax(tp &a,tp b){(b>a)&&(a=b);}
template<typename tp> inline tp pmin(tp a,tp b){return a<b?a:b;}
template<typename tp> inline tp pmax(tp a,tp b){return a<b?a:b;}
template<typename tp>
inline void read(tp &x){
    tp f=1;x=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    x*=f;
}
template<typename tp>
inline void write(tp x,char ed=' '){
    static char stk[40];
    int top=0;
    if(x<0) putchar('-'),x=-x;
    do stk[++top]=x%10+48,x/=10; while(x);
    while(top) putchar(stk[top--]);
    putchar(ed);
}
constexpr unsigned mod1=1'000'000'007,mod2=1'000'000'009;
template<unsigned mod>
unsigned fpow(unsigned x,int p){
    unsigned res=1;
    while(p){
        if(p&1) res=1ull*res*x%mod;
        x=1ull*x*x%mod;
        p>>=1;
    }
    return res;
}
void mian(){
    int n;
    read(n);
    vector<unsigned> a(n+1);
    unsigned lam1=0,lam2=0;
    unsigned pw1=1,pw2=1;
    for(int i=1;i<=n;i++){
        read(a[i]);
        lam1+=1ull*a[i]*pw1%mod1;
        (lam1>=mod1)&&(lam1-=mod1);
        lam2+=1ull*a[i]*pw2%mod2;
        (lam2>=mod2)&&(lam2-=mod2);
        pw1*=2;
        (pw1>=mod1)&&(pw1-=mod1);
        pw2*=2;
        (pw2>=mod2)&&(pw2-=mod2);
    }
    pw1--;
    if(pw1>mod1) pw1=mod1-1;
    pw2--;
    if(pw2>mod2) pw1=mod2-1;
    unsigned inv1=fpow<mod1>(pw1,mod1-2),inv2=fpow<mod2>(pw2,mod2-2);
    lam1=1ull*lam1*inv1%mod1;
    lam2=1ull*lam2*inv2%mod2;
    if(lam1!=lam2){
        puts("-1");
        return;
    }
    vector<ll> c(n);
    //b[i]=c[i]-x;
    c[0]=lam1;
    c[n-1]=2*c[0]-a[n];
    for(int i=n-2;i>=1;i--){
        c[i]=2*c[i+1]-a[i+1];
    }
    ll x=*min_element(c.begin(),c.end());
    if(x<0){
        puts("-1");
        return;
    }
    printf("%lld\n",accumulate(a.begin()+1,a.end(),0ll)-1ll*n*x);
}
int main(){
    int _T;
    read(_T);
    while(_T--) mian();
    return 0;
}

:::