【CF577B Modulo Sum】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15664786.html

题目链接

题目

You are given a sequence of numbers a1, a2, …, an, and a number m.

Check if it is possible to choose a non-empty subsequence aij such that the sum of numbers in this subsequence is divisible by m.

给出 $1$ 个长度为 $n$ 的序列，以及 $1$ 个正整数 $m$。问这个原序列中是否存在非空子序列，使其元素之和能被 $m$ 整除。

思路

该不会有人不知道 $O(nm)$ 的做法吧

先说 $O(nm)$ 做法，相当于是一个01背包，每个数选和不选，然而这样会超时。

于是我们考虑 $n>m$ 的情况。

此时我们对整个数列做前缀和，然后再对 $m$ 取模。

根据抽屉原理，因为 $n>m$，所以在 $n$ 个前缀和中必有两个对 $m$ 取模于是相等，它们中间那段就是答案。

而 $n\leqslant m$ 的情况，$n\leqslant 10^3$，不会超时。

Code

// Problem: CF577B Modulo Sum
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF577B
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
#define N 100010
int n, m, i, j, k; 
int dp[N], f[N], x; 

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
	n=read(); m=read(); 
	if(n>m) return printf("YES"), 0; 
	for(i=1; i<=n; ++i)
	{
		x=read();
		for(j=0; j<m; ++j) f[j]=dp[j];
		for(j=0; j<m; ++j)
			dp[(j+x)%m]+=f[j]; 
		dp[x%m]++; 
	}
	printf("%s", (dp[0] ? "YES" : "NO")); 
	return 0; 
}