Đề bài: $\href{https://codeforces.com/problemset/problem/577/B}{Đây}$
Lời giải: Ở đây ta xét hai trường hợp: $n>m$ và $n<=m$.
+ Nếu $n>m$, chúng ta hãy nhìn vào tổng tiền tố (prefix sums). Theo nguyên lý Dirichlet, tồn tại 2 tổng có cùng số dư chia hết cho m. Chúng ta có thể giả sử đó là $S_{lmodm}=S_{rmodm}$. Khi đó tổng các số trong đoạn $[l+1,r]$ sẽ chia hết cho $m$, vì vậy đáp án trong trường hợp này là YES.
+ Nếu $n<=m$, chúng ta có thể giải quyết bài toán này bằng quy hoạch động trong thời gian $O(m^2)$. Gọi $can[i][r]$ để biểu thị liệu rằng chúng ta có thể tổng bằng $r$ (mod $m$) khi chỉ sử dụng $i-1$ phần tử đầu tiên ($can[i][r]$ bằng $0$ hoặc $1$). Việc cập nhật trong quy hoạch động được thể hiện như sau:
+ Hoặc chúng ta lấy phần tử $a[i]$ và đi đến trạng thái $can[i+1][(r+a[i])\%m]$
+ Hoặc không lấy phần tử $a[i]$ thì chúng ta đi đến trạng thái $can[i+1][r]$.
Nguồn: [Đây](https://codeforces.com/blog/entry/20226)
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define maxn 1000005
- #define maaa 1005
- ll a[maxn],dp[maaa][maaa];
- int main(){
- ll n,m;
- cin>>n>>m;
- ll i;
- for(i=1;i<=n;i++) {
- cin>>a[i];
- a[i]%=m;
- }
- if(n>m){
- cout<<"YES";
- return 0;
- }
- ll r;
- for(r=0;r<m;r++){
- if(a[1]%m==r) dp[2][r]=1; else dp[2][r]=0;
- }
- for(i=2;i<=n;i++){
- for(r=0;r<m;r++) {
- dp[i+1][a[i]%m]=1;
- dp[i+1][(r+a[i])%m]=dp[i][r]|dp[i][(r+a[i])%m];
- }
- }
- /* for(i=2;i<=n+1;i++){
- for(r=0;r<m;r++) cout<<dp[i][r]<<" ";
- cout<<'\n';
- }*/
- if(dp[n+1][0]==1) cout<<"YES";
- else cout<<"NO";
- }
Không có nhận xét nào:
Đăng nhận xét