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;
}
