cf577 B. Modulo Sum

给出(n)个数字，任取一个集合，是否存在一个集合的和是(m)的倍数

我求出前缀和，同时对m取模，如果说(n>m)，根据鹊巢定理那么必定存在两个前缀和的模是相等的。

然后只需要对于(n<1000,m<1000)，进行(n^2)的(01)背包去跑即可
定义(dp[i][j])表示取到第(i)个物品时，大小为(j)的情况是否存在。

初始化(dp[i][a[i]] = 1)
转移方程(dp[i][j] |= dp[i - 1][j]), (dp[i - 1][j + a[i]] |= dp[i - 1][j])

就是01背包的本质吧

int a[N];
bool dp[N][N];
void solve(int kase){
    int n, m;
    scanf("%d%d", &n, &m);
    if(n > m) {
    	printf("YES
"); return;
    }
    bool f = 0;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), f = a[i] == m, a[i] %= m;
    if(f) {
    	printf("YES
"); return;
    }
    for(int i = 1; i <= n; i++) {
    	dp[i][a[i]] = 1;
    	for(int j = 0; j < m; j++) {
    		dp[i][j] |= dp[i - 1][j];
    		dp[i][(j + a[i]) % m] |= dp[i - 1][j];
    	}
    }
    printf("%s
", dp[n][0] ? "YES" : "NO");
}