目录
题目描述
You are given a sequence of numbers 𝑎1,𝑎2,...,𝑎𝑛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 .
输入格式
The first line contains two numbers, 𝑛n and 𝑚m ( 1<=𝑛<=1061<=n<=106 , 2<=𝑚<=1032<=m<=103 ) — the size of the original sequence and the number such that sum should be divisible by it.
The second line contains 𝑛n integers 𝑎1,𝑎2,...,𝑎𝑛a1,a2,...,an ( 0<=𝑎𝑖<=1090<=ai<=109 ).
输出格式
In the single line print either "YES" (without the quotes) if there exists the sought subsequence, or "NO" (without the quotes), if such subsequence doesn't exist.
题意翻译
题面描述
给出 1 个长度为 n 的序列，以及 1 个正整数 m。问这个原序列中是否存在非空子序列，使其元素之和能被 m 整除。
输入格式
第 1 行，有 2 个正整数，分别为原序列的长度 n 和 除数 m。 （数据范围：1 ⩽ 𝑛 ⩽⩽n⩽
，2 ⩽ m ⩽
） 第 2 行，有 n 个自然数，表示该原序列的元素
。 （数据范围：0 ⩽
⩽
）
输出格式
仅 1 行，如果存在符合条件的子序列，输出 YES，否则输出 NO。
样例解释
- 第 1 组样例的解释： 存在符合条件的子序列 {2,3}，其元素之和为 2+3=5，5 可以被 5 整除。
- 第 2 组样例的解释： 由于原序列中只有 1 个元素，因此它只有 1 个子序列 {5}，但显然 5 不可以被 6 整除。
- 第 3 组样例的解释： 存在符合条件的子序列 {3,3}，其元素之和为 3+3=6，6 可以被 6 整除。
- 第 4 组样例的解释： 选择整个原序列作为子序列，其元素之和为 5+5+5+5+5+5=305，30 可以被 6 整除.
样例输入
（内容过多，详见原题链接）
样例输出
（内容过多，详见原题链接）
思路
看到子序列的和我们马上想到 01背包，可是这么大的 n 使我们无从下手。
这道题要求子序列之和能否为 m 的倍数，也就是 mod m 后为 0。
因为若干数之和再取模相当于把每个数取模后求和再取模，所以我们可以把每一个数先模 m。
子数组是子序列的特殊形式...然后子数组是前后两个前缀和之差...前缀和共有n个...！
当前缀和对于 m 取模后的值只可能在 [0,m) 之间，也就是 m 种可能值。
这时候就要运用到抽屉原理了！
这里我们要用到它的一条原理：
把多于n个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。
那我们把 n 个前缀和的值放到 m 个可能值里，如果 n>m ，则必有相同值！
当两个相同值作差，结果为 0，也就是说，它们中间的这一个区间之和必是 𝑚m 的倍数！
好了，n>m 的情况解决完了，剩下就只有 𝑛≤𝑚n≤m 的情况了。
整合一下此时的数据范围：
1≤𝑛≤𝑚≤
n 大大缩小，可以使用 01背包 求解了。
参考代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1005;
int a[N];
bool dp[N][N], f;
int main()
{
/*ios::sync_with_stdio(0);
cin.tie(0);*/
int n, m;
cin >> n >> m;
if(n > m)
{
cout << "YES";
return 0;
}
for(int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] %= m;
}
for(int i = 1; i <= n && !f; i++)
{
dp[i][a[i]] = true;
for(int j = 1; j <= m; j++)
{
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
dp[i][(j + a[i]) % m] = max(dp[i][(j + a[i]) % m], dp[i - 1][j]);
}
f = dp[i][0];
}
if(f)
cout << "YES";
else
cout << "NO";
return 0;
}原理链接：CF 577B Modulo Sum
制作不易，点个关注不迷路。