题解：AT_abc419_e [ABC419E] Subarray Sum Divisibility

· · 题解

前言

题目传送门，官方题解，更低复杂度的官方题解。

这篇题解中，会先讲解 O(LM^2) 的做法，再讨论 O(NM) 的做法。

下文出现的变量，默认有属于自然数集的限制。

题意

给定一个长为 N 的序列，一次操作可以给其中一个数 +1 ，问使其所有长为 L 的连续子序列之和都是 M 的倍数的最小操作数。

解题思路

设原序列为 A，操作结束后的序列为 B。

先根据题意几个式子看一下（在此贴出前两个）：

(\sum_{i=1}^{i\le L}B_i)\bmod M=0 (\sum_{i=2}^{i\le L+1}B_i)\bmod M=0

发现两个式子仅有两个数不同，作差得到：

(B_1-B_{L+1})\bmod M=0

对所有式子进行处理，可以得到：

\forall (i\le L)\land (j\times L+i\le N)，(B_i- B_{j\times L+i})\bmod M=0

也即是说，B 序列中，下标模 L 同余的，原数模 M 同余。为了方便，对于模 L 同余的下标，称它们为强关联下标（每个下标都是其本身的强关联下标）。

由此，我们有这样一个思路：对于一个下标 i\le L，枚举 B_i 的取值，考虑其所有强关联下标 j 由 A_j 改为 B_j 所需的操作数，统计到同一个预处理数组中。可以结合代码理解：

::::info[参考代码]{open}

for(int i=1;i<=n;i++){//cost 即是预处理数组 
    int p=i%l;//意味着后面下标中将会出现 0 
    A[i]=read();
    for(int j=0;j<A[i];j++) cost[p][j]+=j-A[i]+m;
    //操作数的取值有属于自然数的限制 
    for(int j=A[i];j<m;j++) cost[p][j]+=j-A[i];
}

::::

预处理结束后，我们就只用考虑前 L 个下标之间的限制，仅有一个限制：

(\sum_{i=1}^{i\le L}B_i)\bmod M=0

由于下标对 L 求余过，不妨认为下标 L 为下标 0，那么改写过来即是：

(\sum_{i=0}^{i<L}B_i)\bmod M=0

结合预处理，可知这样一个方案的操作数（下称花费）是：

\sum_{i=0}^{i<L}cost_{i,B_i}

容易想到 dp，设 dp_{i,j} 为考虑了下标 \le i 的部分（下标从 0 开始），(\sum_{k=0}^{k\le i}B_k)\bmod M=j 的最小花费，转移方程：

dp_{i,(j+k)\bmod M} \xleftarrow{checkmin} dp_{i-1,j}+cost_{i,k} 由于出现了负数作为下标，我们可以使用滚动数组来避免此问题，代码如下： ::::info[Code] ```cpp #include<bits/stdc++.h> using namespace std; #define N 505 int n,m,l,cost[N][N]; int dp[N],A[N],H[N]; inline int read(){ int a=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) a=10*a+ch-'0',ch=getchar(); return a; } inline void checkmin(int &a,int b){a=min(a,b);} int main(){ n=read(),m=read(),l=read(); for(int i=1;i<=n;i++){ int p=i%l; A[i]=read(); for(int j=0;j<A[i];j++) cost[p][j]+=j-A[i]+m; for(int j=A[i];j<m;j++) cost[p][j]+=j-A[i]; } memset(dp,0x3f,sizeof(dp)),dp[0]=0; for(int i=0;i<l;i++){ memset(H,0x3f,sizeof(H)); for(int j=0;j<m;j++){ for(int k=0;k<m;k++){ int c=j+k;(c>=m)&&(c-=m);//相当于取模 checkmin(H[c],dp[j]+cost[i][k]); } } for(int j=0;j<m;j++) dp[j]=H[j]; } printf("%d",dp[0]); return 0; } ``` :::: 预处理部分的时间复杂度为 $O(NM)$，dp 转移部分的时间复杂度为 $O(LM^2)$，总时间复杂度为 $O(LM^2)$。 ## 更低的时间复杂度 事实上，由于 $cost$ 的值有一定性质，我们可以做到 $O(NM)$ 的时间复杂度。观察预处理部分的代码： ```cpp int p=i%l; A[i]=read(); for(int j=0;j<A[i];j++) cost[p][j]+=j-A[i]+m; for(int j=A[i];j<m;j++) cost[p][j]+=j-A[i]; ``` 发现 $j<A_i$ 时，$cost_{p,j}$ 要多加上一个 $M$，尝试总结（其中 $p$ 与 $i$ 为强关联下标，$p<L$）： $$cost_{p,j}=\sum_{i}j-A_i+[j<A_i]\times M$$ 基于上式，设 $siz_p=\sum_{i}1$，$t=\sum_{i}[j<A_i]$，$c=\sum_{i}A_i$，则： $$cost_{p,j}=siz_p\times j-c+t\times M$$ 对于一个固定的 $p$，随着 $j$ 的增长，$t$ 单调不增，$siz_p$ 和 $c$ 都是定值，视 $cost_{p,j}$ 为一个关于 $j$ 的函数，那么，在平面直角坐标系中，$t$ 的取值随 $j$ 变化，使函数分段，每一段内都是一个一次函数。 那么，在转移的时候，我们只需要在分段的点上去使用 $cost$ 数组转移，其余部分可以利用 $siz$ 快速转移， 由于 $t$ 至多有 $siz$ 种取值，即只用特殊转移 $siz$ 处， 又 $\sum_{p<L}siz_p=N$，故只用特殊转移 $N$ 处，每处按原方法转移，时间复杂度 $O(NM)$。 快速转移部分，由于模意义下数轴会形成一个环，需要破环成链，那么对于所有 $0\le j<2\times M$，进行如下转移： $$dp_{i,(j+1)\bmod M} \xleftarrow{checkmin} dp_{i,j\bmod M}+siz_i$$ 注意应先进行特殊转移，利用特殊转移的结果来快速转移，事实上，快速转移可以看作对特殊转移中使用的 $cost$ 数组的一种延续，这是基于一次函数的。 总时间复杂度降至 $O(NM)$。 ::::info[Code] ```cpp #include<bits/stdc++.h> using namespace std; #define N 505 int n,m,l,cost[N][N]; int dp[N],A[N],H[N]; vector<int>sp[N];//special，存特殊点 inline int read(){ int a=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) a=10*a+ch-'0',ch=getchar(); return a; } inline void checkmin(int &a,int b){a=min(a,b);} int main(){ n=read(),m=read(),l=read(); for(int i=1;i<=n;i++){ int p=i%l; A[i]=read(),sp[p].push_back(A[i]); for(int j=0;j<A[i];j++) cost[p][j]+=j-A[i]+m; for(int j=A[i];j<m;j++) cost[p][j]+=j-A[i]; } memset(dp,0x3f,sizeof(dp)),dp[0]=0; for(int i=0;i<l;i++){ memset(H,0x3f,sizeof(H)); int siz=sp[i].size(); for(int j=0;j<m;j++){ for(auto &v:sp[i]){ checkmin(H[(v+j)%m],dp[j]+cost[i][v]); } } for(int j=0;j<2*m;j++){ checkmin(H[(j+1)%m],H[j%m]+siz); } for(int j=0;j<m;j++) dp[j]=H[j]; } printf("%d",dp[0]); return 0; } ``` :::: ## 总结 遇到一些和数学有一定关系的题目，要先推一些式子，不要和蒟蒻一样在那里毫无根据乱想用什么算法，导致后面式子推出来了但差 30 秒调好代码。 做优化的时候，注意挖掘性质，这一点需要多加练习。