题解：CF1237G Balanced Distribution

· · 题解

又名：如何将简单的证明变得又臭又长且仅仅是看上去高级一点。

1 分析

定义 1.1

定义一个函数 \text{Sum}(l,r,a) (l \leq r,l,r \in [1,n])，满足：

\text{Sum}(l,r,a)=\sum_{i=l}^{r}a_i

定义 1.2

定义每个位置的目标状态为 s，满足：

s=\dfrac{\text{Sum}(1,n,a)}{n}

定理 1.1

对于区间 [l,r]，若满足 \text{Sum}(l,r,a)=(r-l+1)\times s，则至多 \left\lceil \dfrac{r-l}{k-1} \right\rceil 次分配操作使得 \forall i \in [l,r],a_i=s 且其余数值不变。

证明 1.1

进行操作：

对于 \forall i \in [1,n] , a_i \to a_i-s。

此时原定理等价于：

对于区间 [l,r]，若满足 \text{Sum}(l,r,a)=0，则至多 \left\lceil \dfrac{r-l}{k-1} \right\rceil 次分配操作使得 \forall i \in [l,r],a_i=0 且其余数值不变。

定义 1.1.1

定义一个函数 f(l,r,x,a,t) 表示是否满足至多 t 次操作使得 a_l=x,\forall i \in [l+1,r],a_i=0 且其余数值不变。

特殊的，f(l,l,x,a,0)=[a_l=x]。

定理成立等价于若满足 f(l,r,0,a,\left\lceil \dfrac{r-l}{k-1} \right\rceil)=1。

考虑任意情况下的 f(l,r,x,a,t)。

  1. r-l+1 \leq k
f(l,r,x,a,t)=[x=\text{Sum}(l,r,a)][t \geq 1]

具体的，若满足 x=\text{Sum}(l,r,a)，则对 [l,l+k-1] 进行一次分配操作。

分配后的数值满足：

a_l=x \forall i \in [l+1,r],a_i=0

区间 [r+1,l+k-1] 中的数不变。

  1. \text{Sum}(l,l+k-1,a) \geq x

定义 1.1.2

定义一个数组 b，满足

b_l=x \forall i \in [l+1,l+k-1),b_i=0 b_{l+k-1}=\text{Sum}(l,l+k-1,a)-x \forall i \in [1,l)\wedge(l+k-1,n] ,b_i=a_i f(l,r,x,a,t)=f(l+k-1,r,0,b,t-1)

具体的，先对 [l,l+k-1] 进行一次分配操作。

分配后的数值满足：

a_l=x \forall i \in [l+1,l+k-1),a_i=0 a_{l+k-1}=\text{Sum}(l,l+k-1,a)-x

分配后的 a 数组即变成 b 数组。

此时再对后面的部分进行操作，等价于 f(l+k-1,r,0,b)。

  1. \text{Sum}(l,l+k-1,a) < x
f(l,r,x,a,t)=f(l+k-1,r,a_{l+k-1}+x-\text{Sum}(l,l+k-1,a),a,t-1)

具体的，先对 [l+k-1,r] 进行分配操作。

分配后的数值满足：

a_{l+k-1}=a_{l+k-1}+x-\text{Sum}(l,l+k-1,a),a) \forall i \in (l+k-1,r] , a_i=0

能否完成等价于 f(l+k-1,r,a_{l+k-1}+x-\text{Sum}(l,l+k-1,a),a,t-1)。

此时对 [l,l+k-1] 进行一次分配操作。

分配后的数值满足：

a_{l}=x \forall i \in (l,l+k-1] , a_i=0

考虑待证命题 f(l,r,0,a,\left\lceil \dfrac{r-l}{k-1} \right\rceil)=1。

通过上述 3 种情况对原问题进行归纳。

性质 1.1.1

对于情况 2,3 将 f(l,r,x,a,t) 归纳为 f(l',r',x',a',t') 时，满足 r'-l'=r-l-(k-1)。

性质 1.1.2

对于情况 2,3 将 f(l,r,x,a,t) 归纳为 f(l',r',x',a',t') 时，满足 \text{Sum}(l',r',a')=\text{Sum}(l',r',a)。

性质 1.1.3

对于情况 2,3 将 f(l,r,x,a,t) 归纳为 f(l',r',x',a',t') 时，满足 x'+\text{Sum}(l,r,a)-\text{Sum}(l',r',a)=x。

由性质 1.1.1 可得，在变成情况 1 前归纳次数不超过 \left\lceil \dfrac{r-l}{k-1} \right\rceil-1，因此在得到情况 1 时 [t \geq 1] 总是满足。

由性质 1.1.2，1.1.3 可得，由于初始状态 \text{Sum}(l,r,a)=x=0 ，每次归纳后得到的 f(l',r',x',a',t') 总是满足 \text{Sum}(l',r',a')=\text{Sum}(l',r',a)=x'+\text{Sum}(l,r,a)-x=x'，因此在得到情况 1 时 [x=\text{Sum}(l,r,a)] 总是满足。

总上，f(l,r,0,a,\left\lceil \dfrac{r-l}{k-1} \right\rceil)=1，原命题得证。

定理 1.2

对于相邻的两个区间 [l_1,r_1],[l_2,r_2] (1\leq l_1 \leq r_1 \le1 n,1 \leq l_2 \leq r_2 \leq n,l_2=r_1+1)，满足

\text{Sum}(l_1,r_1,a)=(r_1-l_1+1)\times s \text{Sum}(l_2,r_2,a)=(r_2-l_2+1)\times s

，若分别操作的次数小于将两个区间合并为一个区间操作的次数，当且仅当两个区间的 \text{len}-1 为 k-1 的倍数。

形式化的，若满足

\left\lceil \dfrac{\text{len}_1-1}{k-1} \right\rceil+\left\lceil \dfrac{\text{len}_2-1}{k-1} \right\rceil < \left\lceil \dfrac{\text{len}_1+\text{len}_2-1}{k-1} \right\rceil

当且仅当

\text{len}_1-1 \equiv 0 \pmod {k-1} \text{len}_2-1 \equiv 0 \pmod {k-1}

证明 1.2

定义 1.2.1

定义 r_1,r_2 表示区间长度除以 k-1 的余数，即：

\text{len}_1-1 \equiv r_1 \pmod {k-1} \text{len}_2-1 \equiv r_2 \pmod {k-1}

可以得到

\text{len}_1 + \text{len}_2-1 \equiv r_1+r_2+1 \pmod {k-1}

原定理等价于：

\left\lceil \dfrac{r_1}{k-1} \right\rceil+\left\lceil \dfrac{r_2}{k-1} \right\rceil < \left\lceil \dfrac{r1+r2+1}{k-1} \right\rceil

由定义可得

r_1,r_2 \in [0,k-1) r_1+r_2+1 \in [1,2k-2)

因此

1 \leq \left\lceil \dfrac{r1+r2+1}{k-1} \right\rceil \leq 2

分两种情况讨论。

  1. \left\lceil \dfrac{r1+r2+1}{k-1} \right\rceil =1

此时若 \left\lceil \dfrac{r_1}{k-1} \right\rceil+\left\lceil \dfrac{r_2}{k-1} \right\rceil < \left\lceil \dfrac{r1+r2+1}{k-1} \right\rceil，当且仅当 \left\lceil \dfrac{r_1}{k-1} \right\rceil = \left\lceil \dfrac{r_2}{k-1} \right\rceil = 0，即 r_1 = r_2 = 0，即

\text{len}_1-1 \equiv 0 \pmod {k-1} \text{len}_2-1 \equiv 0 \pmod {k-1}
  1. \left\lceil \dfrac{r1+r2+1}{k-1} \right\rceil = 2

此时若 \left\lceil \dfrac{r_1}{k-1} \right\rceil+\left\lceil \dfrac{r_2}{k-1} \right\rceil < \left\lceil \dfrac{r1+r2+1}{k-1} \right\rceil，即 \left\lceil \dfrac{r_1}{k-1} \right\rceil + \left\lceil \dfrac{r_2}{k-1} \right\rceil \leq 1，则总是满足 r_1=0 或 r_2=0。不失一般性的，设 r_1=0，则 r_1+r_2+1=r_2+1 \in [1,k) \leq k-1，因此 \left\lceil \dfrac{r1+r2+1}{k-1} \right\rceil = 1，与条件不符，因此此情况不可能发生。

总上，原定理成立。

对原问题的分析

将原数组分为若干个区间 [l_i,r_i]，满足

\text{Sum}(l_i,r_i,a)=(r_i-l_i+1)\times s

答案为

\sum_{i} \left\lceil \dfrac{r_i-l_i}{k-1} \right\rceil

由定理 1.2 可得，可以一直合并区间直到满足

\text{len}-1 \equiv 0 \pmod {k-1}

此时答案为

\sum_{i} \dfrac{r_i-l_i}{k-1} = \dfrac{n}{k-1} - \sum_{i} \dfrac{1}{k-1}

因此答案与区间数量成负相关，贪心地尽可能多的划分区间即可。

具体的，对于 i，找到最大的 j 满足

j \leq i \text{Sum}(j,i,a)=(i-j+1)\times s i-j \equiv 0 \pmod {k-1}

则划分出区间 [i,j]。

证明 1.3

考虑反证。

设存在 p，满足

p < j \leq i \text{Sum}(p,i,a)=(i-p+1)\times s i-p \equiv 0 \pmod {k-1}

使得划分 [p,i] 更优。

则

\text{Sum}(p,j-1,a)=(j-1-p+1)\times s j-1-p \equiv 0 \pmod {k-1}

此时可以划分出区间 [p,j-1]。

因此原方案中对于 [1,p-1] 和 [i+1,n] 部分采用与现方案相同的划分方式，而原方案中 [p,i] 可以划分为两个区间，现方案中只划分为了一个区间。与现方案比原方案更优的假设不符。

因此划分区间 [i,j] 最优。

2 实现

考虑如何实现上述贪心过程找到每个 i 匹配的端点 j。

进行操作：

对于 \forall i \in [1,n] , a_i \to a_i-s。

此时对于 i，满足条件的 j 可以刻画为

\text{Sum}(j,i,a)=0 i \equiv j \pmod {k-1}

条件一可以重新刻画为

\text{Sum}(1,j-1,a)=\text{Sum}(1,i,a)

因此维护二元组 (\text{Sum}(1,i,a),i \bmod k-1)，j 即为最大的下标，满足

j \leq i (\text{Sum}(1,j-1,a),j \bmod k-1)=(\text{Sum}(1,i,a),i \bmod k-1)

使用 map 记录每个二元组最近一次出现的位置即可，时间复杂度 O(n \log n)。

由于原题中数组成环，最后枚举起点，可以实现 O(n^2) 的算法。

考虑倍增加速，计算 f_{i,j} 表示以 i 为起点划分 2^j 个区间的端点，可以将原算法改进为 O(n \log n)。

输出方案参照证明 1.1 中将问题化归的方式递归即可，时间复杂度 O(n)。

总时间复杂度 O(n \log n)。

3 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int Tim=1;
const int N=2e5+5;
int n,k;
int a[N];
int s;
int nxt[N][20];
map<pair<int,int>,int> vis;
void print(int l,int r,int x){
    if(l==r){
        return;
    }
    if(r-l+1<=k){
        a[(l-1)%n+1]=x;
        for(int i=l+1;i<=r;i++){
            a[(i-1)%n+1]=0;
        }
        cout<<(l-1)%n<<' ';
        for(int i=l;i<l+k;i++){
            cout<<a[(i-1)%n+1]+s<<' ';
        }
        cout<<'\n';
        return;
    }
    int sum=0;
    for(int i=l;i<l+k;i++){
        sum+=a[(i-1)%n+1];
    }
    if(sum>=x){
        a[(l-1)%n+1]=x;
        for(int i=l+1;i<l+k-1;i++){
            a[(i-1)%n+1]=0;
        }
        a[(l+k-1-1)%n+1]=sum-x;
        cout<<(l-1)%n<<' ';
        for(int i=l;i<l+k;i++){
            cout<<a[(i-1)%n+1]+s<<' ';
        }
        cout<<'\n';
        print(l+k-1,r,0);
        return;
    }
    print(l+k-1,r,a[(l+k-1-1)%n+1]+x-sum);
    a[(l-1)%n+1]=x;
    for(int i=l+1;i<l+k;i++){
        a[(i-1)%n+1]=0;
    }
    cout<<(l-1)%n<<' ';
    for(int i=l;i<l+k;i++){
        cout<<a[(i-1)%n+1]+s<<' ';
    }
    cout<<'\n';
}
void Solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s+=a[i];
    }
    s/=n;
    for(int i=1;i<=n;i++){
        a[i]-=s;
        a[i+n]=a[i];
    }
    for(int i=1,sum=0;i<=2*n;i++){
        sum+=a[i];
        nxt[i][0]=vis[{sum,(i-1)%(k-1)}];
        vis[{sum,i%(k-1)}]=i;
        for(int j=1;j<=18;j++){
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
        }
    }
    int ans=(n-1+k-1-1)/(k-1),pos=-1;
    for(int r=n+1;r<=2*n;r++){
        int l=r,tot=0;
        for(int j=18;j>=0;j--){
            if(nxt[l][j]>=r-n){
                l=nxt[l][j];
                tot+=(1<<j);
            }
        }
        int len=r-l;
        int res=(len-tot)/(k-1)+(n-len+k-1-1)/(k-1);
        //cout<<r<<':'<<res<<' '<<len<<' '<<tot<<'\n';
        if(res<ans){
            ans=res;
            pos=r;
        }
    }
    cout<<ans<<'\n';
    if(pos==-1){
        print(1,n,0);
        return;
    }
    int r=pos;
    while(r>pos-n){
        int l=max(pos-n,nxt[r][0]);
        print(l+1,r,0);
        r=l;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    // cin>>Tim;
    while(Tim--){
        Solve();
    }
    return 0;
}