Skip to content

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\)行,每行输出YESNO,代表满足条件的连续子序列是否存在

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;
}