[USACO16JAN] Subsequences Summing to Sevens S

OJ: luogu

题目 ID: P3131

标签: 数论前缀和

日期: 2025-12-31 15:35

题目解析

核心思想:

7abab(mod7) 7 \mid a -b \Leftrightarrow a \equiv b \pmod 7

暴力代码

cpp
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int n;
int s[maxn];
int ans;

int main(int argc, char const *argv[])
{
    cin >> n;
    for(int i =1;i<=n;i++) {
        cin >> s[i];
        s[i] += s[i-1];// si  = si-1 + a[i]
    }

    for(int i =1;i<=n;i++) {
        for(int j = i;j<=n;j++)
        {
            // cout << i<< " " << j << endl;
            int t= s[j] - s[i-1];
            if( t % 7 == 0) {
                int len = j-i+1;
                if( ans < len)
                    ans = len;
            }
        }
    }
    cout << ans;
    return 0;
}

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2025-12-31 16:46:37
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const ll maxn = 2e6+5;
ll n,m;
ll a[maxn];
ll pre[maxn];
ll first[10];
ll last[10];


signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    std::cin >> n;
    for(ll i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
        pre[i] = pre[i-1] + a[i];
    }
    // 7 | a -b 
    // a \equiv b \pmod 7
    for(ll i = 0;i <= 6 ;++i ) // i: 0->6
    {
        last[i] = first[i] = -1; // 表示不存在
    }

    // 特殊判断
    first[0] = last[0] = 0;

    for(ll i = 1;i <= n ;++i ) // i: 1->n
    {
        ll mod = pre[i] % 7;
        if( first[mod] == -1) first[mod] =  i;
        last[mod] = i;
    }

    ll ans = -1;
    for(ll i = 0;i <= 6 ;++i ) // i: 0->6
    {
        ll len = last[i] - first[i];
        if( ans < len) ans = len;
    }
    std::cout << ans << "\n";

    return 0;
}