Thứ Ba, 3 tháng 11, 2020

Cho một mảng gồm n phần tử, kiểm tra xem có tồn tại một subsequence (rời rạc) chia hết cho m hay không ?

Đề 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)


  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define maxn 1000005
  5. #define maaa 1005
  6. ll a[maxn],dp[maaa][maaa];
  7. int main(){
  8. ll n,m;
  9. cin>>n>>m;
  10. ll i;
  11. for(i=1;i<=n;i++) {
  12. cin>>a[i];
  13. a[i]%=m;
  14. }
  15. if(n>m){
  16. cout<<"YES";
  17. return 0;
  18. }
  19. ll r;
  20. for(r=0;r<m;r++){
  21. if(a[1]%m==r) dp[2][r]=1; else dp[2][r]=0;
  22. }
  23. for(i=2;i<=n;i++){
  24. for(r=0;r<m;r++) {
  25. dp[i+1][a[i]%m]=1;
  26. dp[i+1][(r+a[i])%m]=dp[i][r]|dp[i][(r+a[i])%m];
  27. }
  28. }
  29. /* for(i=2;i<=n+1;i++){
  30. for(r=0;r<m;r++) cout<<dp[i][r]<<" ";
  31. cout<<'\n';
  32. }*/
  33. if(dp[n+1][0]==1) cout<<"YES";
  34. else cout<<"NO";
  35. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...