14222: 【原4222】Dynamic Additive Test
题目
题目描述
author: zms 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4222
Description
MoLe有\(T\)个由许多正整数构成的序列\(A\)。有一天MoLe找了一个有趣的正整数\(m\)。MoLe想知道在\(A\)的所有连续子序列中是否存在一个连续子序列其和是m的倍数。然而遍历整个序列的所有连续子序列太费时了。MoLe希望你来验证这个子序列的存在性。
Input Format
第一行一个整数\(T\),代表序列的个数
接下来\(2T\)行,第\(2i\)行两个整数\(n,m\),分别为序列的大小和MoLe的有趣的正整数\(m\)的值。接下来一行\(n\)个正整数,为原序列的元素。
Output Format
输出共\(T\)行,每行输出YES
或NO
,代表满足条件的连续子序列是否存在
Sample Input
1
3 5
1 2 3
Sample Output
YES
Limit
对于\(40\%\)的数据,满足\(n \leq 10^3, m\leq 10^4\)
对于\(100\%\)的数据,满足\(n \leq 5 * 10^5, m \leq 10^6, T \leq 5\)
ligongzzz's solution
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for (; t; --t) {
int n, m;
cin >> n >> m;
vector<bool> mdata(m, false);
mdata[0] = true;
int cur_sum = 0;
bool flag = false;
for (int i = 0; i < n; ++i) {
int temp;
cin >> temp;
if (flag)
continue;
cur_sum = (cur_sum + temp) % m;
if (mdata[cur_sum]) {
flag = true;
}
else
mdata[cur_sum] = true;
}
if (flag)
cout << "YES\n";
else
cout << "NO\n";
}
return 0;
}