CF1740I Arranging Crystal Balls

Kubic · 2022-10-31 17:08:03 · 题解

这是一个我花了 1.5h 思考出的比标算更优的做法，目前未经过卡常的代码获得了 CF 最优解。

设 b_i=(a_i-a_{(i+n-1)\bmod n})\bmod m。

我们可以从 i 向 (i+k)\bmod n 连边，这样我们会得到 d=\gcd(n,k) 个长度为 l=\dfrac{n}{d} 的环。

那么每次操作即为在某个环上选择相邻两个数分别 +1,-1，其中某些操作会对 a_0 有影响。一个环上对 a_0 有影响的操作位置数量恰好为 \dfrac{k}{d}。

对于一个环，设它上面的数依次为 c_{0\dots l-1}，设 s 为 c 的前缀和。

不妨设 c_0 和 c_{l-1} 之间的操作不会对 a_0 产生影响。

设 c_0 和 c_{l-1} 之间的操作最终使得 c_0\leftarrow (c_0+t)\bmod m,c_{l-1}\leftarrow (c_{l-1}-t)\bmod m。

枚举 t 之后我们就可以断环为链。设 s'_i=(s_i+t)\bmod m。

之后每次操作对 s' 的影响为 s'_i\leftarrow s'_i+1 或 s'_i\leftarrow s'_i-1，其中 i\in [0,l-2]。而如果 i 这个位置的操作会对 a_0 产生影响，那么 a_0 的变化量与 s'_i 的变化量是一致的。

最少的操作次数即为 \sum\limits_{i=0}^{l-2}\min\{s'_i\bmod m,m-s'_i\bmod m\}。

设这个环在 t=0 时的操作会使得 a_0\leftarrow (a_0+\Delta)\bmod m。

可以得到，对于任意 t，它会使得 a_0\leftarrow (a_0+\Delta-\dfrac{kt}{d})\bmod m。

我们可以对每个环事先计算出 \Delta，并将它们的影响统计到 a_0 上。设此时 a_0 变为 a'_0。设所有环的 t 之和为 t_0，我们要求 a'_0=\left(\dfrac{kt_0}{d}\right)\bmod m，只需要满足这个条件就可以使得最终 a'_0=0。

因此我们可以依次考虑每个环，对于每个 t 求出 w_t=\min\{t,m-t\}+\sum\limits_{i=0}^{l-2}\min\{(s_i+t)\bmod m,m-(s_i+t)\bmod m\}。

设 dp_i 表示当前 t_0\bmod m=i 的最小总代价，每次计算出一个环的 w 之后我们将这个环的贡献通过背包计入 dp 中即可。

时间复杂度 O(dm^2)。但这不够优秀。

考虑一个环的 w 有什么性质。可以发现 \min\{t,m-t\} 和 \min\{(s_i+t)\bmod m,m-(s_i+t)\bmod m\} 都是只有 O(1) 段的分段一次函数，因此 w 可以被分为 O(l) 段等差数列。

可以使用单调队列在 O(m) 的时间内计算一段等差数列对 dp 的贡献。时间复杂度被优化为 O(dlm)=O(nm)。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define LIM 10000005
#define ll long long
#define gc() (P1==P2 && (P2=(P1=buf)+fread(buf,1,LIM,stdin),P1==P2)?EOF:*P1++)
const ll INF=1e18;char buf[LIM],*P1=buf,*P2=buf;
int n,n1,m,c,d,tp,gl,a[N],a1[N],b[N],q[N];
ll ans,w[N],dp[N],tmp[N*2];struct Node {int l,r;ll w;}z[N];
int rd()
{
    int res=0;char c=0;while(!isdigit(c)) c=gc();
    while(isdigit(c)) res=res*10+(c-48),c=gc();return res;
}
int gcd(int x,int y) {return y?gcd(y,x%y):x;}
int main()
{
    n=rd();m=rd();c=rd();d=gcd(n,c);n1=n/d;
    for(int i=0;i<n;++i) a1[i]=rd();gl=a1[n-1];
    for(int i=0;i<n;++i) a[(i+1)%n]=(a1[(i+1)%n]-a1[i]+m)%m;
    ans=INF;for(int i=1;i<m;++i) dp[i]=INF;
    for(int i=0,t;i<d;++i)
    {
        for(int j=0;j<n1;++j)
        {
            t=(i+1ll*j*c)%n;b[j]=a[t];if(j) b[j]=(b[j]+b[j-1])%m;
            if(t+c>=n) gl=(gl-b[j]+m)%m;
        }if(b[n1-1]) {printf("-1\n");return 0;}for(int j=0;j<m;++j) w[j]=min(j,m-j);
        for(int j=0;j<n1-1;++j) for(int k=0;k<m;++k) t=(b[j]+k)%m,w[k]+=min(t,m-t);
        tp=0;z[++tp]=(Node) {0,0,w[1]-w[0]};
        for(int j=2;j<m;++j) if(w[j]-w[j-1]!=z[tp].w)
            z[tp].r=j-1,z[++tp]=(Node) {j,0,w[j]-w[j-1]};z[tp].r=m-1;
        for(int j=0;j<m*2;++j) tmp[j]=INF;
        for(int j=1,l,r;j<=tp;++j)
        {
            q[0]=2;q[1]=1;l=z[j].l;r=z[j].r;
            for(int k=l;k<m+r;++k)
            {
                while(q[0]<=q[1] && q[q[0]]<k-r) ++q[0];
                if(k-l<m)
                {
                    while(q[0]<=q[1] && dp[k-l]<=dp[q[q[1]]]+z[j].w*(k-l-q[q[1]]))
                        --q[1];q[++q[1]]=k-l;
                }if(q[0]<=q[1]) tmp[k]=min(tmp[k],dp[q[q[0]]]+w[k-q[q[0]]]);
            }
        }for(int j=0;j<m;++j) dp[j]=min(tmp[j],tmp[m+j]);
    }for(int i=0;i<m;++i) if(gl==1ll*c/d*i%m) ans=min(ans,dp[i]);
    if(ans<INF) printf("%lld\n",ans);else printf("-1\n");return 0;
}