AT_abc419_e [ABC419E] Subarray Sum Divisibility

hjqhs · 2025-10-16 19:51:35 · 个人记录

米奇妙妙题。
容易观察到下标对 L 取模分成 L 类，每类对 m 取模应相等，可以预处理。
然后只用考虑前 L 个数，f_{i,j} 为前 i 个数之和对 m 取模所需最小次数。这个过程类似于 dp。

// Problem: Subarray Sum Divisibility
// Contest: Virtual Judge - AtCoder
// URL: https://vjudge.net/problem/AtCoder-abc419_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Created Time: 2025-10-15 19:17:34
// Author: hjqhs
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
typedef long long ll;
typedef unsigned long long ull;
const int N = 505;
const int INF = 0x3f3f3f3f;
int n, m, l, a[N], s[N][N], f[N][N];
void solve() {
    cin >> n >> m >> l; rep(i, 1, n) cin >> a[i];
    rep(i, 1, l) rep(j, 0, m - 1) for(int k = i; k <= n; k += l) s[i][j] += (j - a[k] + m) % m;
    memset(f, INF, sizeof(f)); f[0][0] = 0;
    rep(i, 0, l - 1) rep(j, 0, m - 1) rep(k, 0, m - 1)
        f[i + 1][(j + k) % m] = min(f[i + 1][(j + k) % m], f[i][j] + s[i + 1][k]);
    cout << f[l][0] << '\n'; 
    return;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T --) solve();
    return 0;
}