题解：P12557 [UOI 2024] Football

__FL__ · 2026-07-22 19:29:49 · 题解

Solution

为方便，我们令球员编号从 0 开始，设 s 为 a 的前缀和数组。

考虑刻画对于各个 i，所有能够拿到球的人的分布情况。

易知对一个 i，所有能取到的人包括：

容易证明存在 k 使得 k\cdot s_i\bmod n = \gcd(s_i,n)，故该式等价于：

一个关键的观察是，n 的因子数是少的，它总是 <<\sqrt n，事实上 3\times 10^5 内的数最多只有 180 个因子（277200）。所以我们可以枚举 n 的因数，单独统计每个因数的各个余数所对应的答案。令 mn_{i,j} 为所有模 i 余 j 的位置的 \min，对于位置 i，枚举 n 的因子 j，mn_{j,s_i\bmod j} 对 ans_j 产生贡献，答案即为 ans_{\gcd(s_i,n)}。mn 容易预处理。

时间复杂度为 O((n+q)\text d(n))，其中 \text d(n) 为 n 的因子数。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 300005,M = 998244353;
int n,m,q,c[N],a[N],sum[N],mn[185][N],f[185],re[N];
vector<int>vec;
int gcd(int a,int b)
{
    if (!b) return a;
    return gcd(b,a%b);
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++)
        cin >> c[i];
    for (int i = 1; i <= q; i++)
        cin >> a[i],sum[i] = (sum[i-1]+a[i])%n;
    for (int i = 1; i <= n; i++)
        if (n%i == 0) vec.push_back(i);
    m = vec.size();
    for (int i = 0; i < m; i++)
        re[vec[i]] = i;
    memset(mn,0x3f,sizeof mn);
    memset(f,0x3f,sizeof f);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            mn[i][j%vec[i]] = min(mn[i][j%vec[i]],c[j]);
    for (int i = 1; i <= q; i++)
    {
        for (int j = 0; j < m; j++)
            f[j] = min(f[j],mn[j][sum[i]%vec[j]]);
        cout << f[re[gcd(sum[i],n)]] << ' ';
    }
    return 0;
}