有点耻辱，打比赛的时候去吃饭了，最后赛后 20 分钟就把 E 题写出来了……还给我掉了分╥﹏╥…又被 ABC 做局了。

题目大意

给定长为 $N$ 的整数序列，每次操作可以将单个元素加一，求至少多少次操作，使得每个长为 $L$ 的子段和为 $M$ 的倍数。

题目分析

让每个固定长度的子段和为一个数的倍数……这一眼就很数学，或者说很有规律啊。我们发现，如果有
$$\sum_{i=k}^{k+L-1}a_i\equiv \sum_{i=k+1}^{k+L}a_i\equiv0\pmod{M}$$
那恒等式两边减去公共部分 $\sum_{i=k+1}^{k+L-1}a_i$，就有
$$a_k\equiv a_{k+L}\pmod{M}$$
那我们就可以把每隔 $L$ 个的数分为一类，每类的数字对 $M$ 取模相同。那这样，我们只需要把前 $L$ 项的数算出，就可以用把剩下的都算出来了。

只用算前 $L$ 项，观察到 $L\leq N,M\leq500$，我们可以枚举每一项和前一项模 $M$ 的余数，就可使用动态规划进行状态转移（一眼 dp）。

令 $dp_{i,j}$ 表示使前 $i$ 项的和对 $M$ 取模为 $j$ 的最小操作数，$sum_{i,j}$ 表示把和 $i$ 同类的数对 $M$ 的余数都改为 $j$ 的最小操作数（ $sum$ 可以直接枚举算），那么转移式如下
$$ dp_{i, (j+k) mod \ M}= \min (dp_{i-1,k}+sum_{i,j}) $$
其中 $k$ 表示前一项模 $M$ 的余数，$(j+k) mod \ M$ 表示这一项模 $M$ 的余数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
const int N=505; 
int n,m,l,a[N],ans,dp[N][N],sum; 
vector<int> c[N];
signed main(){
    memset(dp,0x3f,sizeof(dp));
    cin>>n>>m>>l;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=l;i++)
        for(int j=i;j<=n;j+=l) 
            c[i].push_back(a[j]); 
    dp[0][0]=0; 
    for(int i=1;i<=l;i++) 
        for(int j=0;j<m;j++){
            sum=0;
            for(int k:c[i]) sum+=(j-k+m)%m;
            for(int k=0;k<m;k++)
                dp[i][(j+k)%m]=min(dp[i][(j+k)%m],dp[i-1][k]+sum);
        }
    cout<<dp[l][0];
    return 0;
}