CF 577 B. Modulo Sum 鸽巢原理/01背包 (*1800)

showball / 2024-10-09 / 原文

CF 577 B. Modulo Sum 鸽巢原理/01背包

题目链接

思路：

每个数可选可不选，经典的01背包问题，但是数据范围过大，因为要找可行解即可，考虑去找满足题意的子数组(子数组是特殊的子序列)。就变成一个经典的前缀和问题。只需要找到前缀和数组中存在两个相等的值，那么满足条件。由于需要取模，那么前缀和结果只有 $[0,m)$ 这 $m$ 种情况。那么根据 鸽巢原理 显然当 $n>m$ 时，一定有解。这样我们只需要考虑 $n\le m$ 的情况，数据范围就缩小了，01背包处理即可。

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=m;
    } 
    if(n>m) return cout<<"YES\n",void();
    vector<vector<int>> dp(n+1,vector<int>(m+1));
    
    bool ok=false;
    for(int i=1;i<=n;i++){
        dp[i][a[i]]=1;
        for(int j=1;j<=m;j++){
            dp[i][j]|=dp[i-1][j];
            dp[i][(j+a[i])%m]|=dp[i-1][j];
        }
        ok|=dp[i][0];
    }
    cout<<(ok?"YES\n":"NO\n");
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}