codeforces 577B B. Modulo Sum(背包+dp)

题目链接：

codeforces 577B

---

题目大意：

给出n个数，求是否存在一个子集，这个子集中的数的和能够整除m

---

题目分析：

• 定义状态dp[i][j]代表利用前i个数是否能够得到对m取模得j。
• 转移的过程采取背包的方法，很水
• 但是直接做一定会超时， O(n⋅m)
• 利用鸽巢定理可以知道，当n>m时，有n个数便有n个前缀和，而n%m只有m-1个值，所以至少有两个余数相同的前缀和，那么便能够得到一个连续的子序列满足题设条件，所以n>m的情况特判，复杂度就会优化为 O(m⋅m)
  

  ---

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 1007

using namespace std;

int n,m;
int a[MAX*MAX];
int dp[MAX][MAX];

int main ( )
{
    scanf ( "%d%d" , &n , &m );
    for ( int i = 1 ; i <= n ; i++ )
        scanf ( "%d" , &a[i] );
    if ( n > m )
    {
        puts ("YES" );
        return 0;
    }
    memset ( dp , 0 , sizeof ( dp ) );
    dp[0][0] = 1;
    bool flag = false;
    for ( int i = 1 ; i <= n ; i++ )
        for ( int j = m-1; j >= 0; j-- )
        {
            int x = ((j-a[i])%m+m)%m;
            if ( dp[i-1][x] )
            {
                dp[i][j] = 1;
                if ( j == 0 ) 
                    flag = true;
            }
            if ( dp[i-1][j] )  dp[i][j] = 1;
        }
    if ( flag ) puts ("YES");
    else puts ("NO"); 
}