Skip to content

14158: 【原4158】失败和

题目

题目描述

author: 失败 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4158

Description

失败者不需要体面。

XYF想知道这个世界上有没有像SQD一样失败的人。相传有一种测试一个人是否失败的方法,那就是让他随机写下一串数字。如果这串数字的某个连续子序列的和为失败数的倍数,那么这个连续子序列被称为一个失败证据。

现在请成功的你编写一个程序来帮助XYF计算一串数字中失败证据的数量。

Input Format

第一行为数据的组数T。

第二行开始是数据,每组数据两行。

其中第一行是两个整数n、 m。n是数字串的长度,m为失败数。

第二行有n个正整数x( \( 1 \leq x \leq 100 \) ),表示这串数字。

Output Format

输出T行,每行输出该组失败证据的数量。

Sample Input

2

3 3

1 2 3

5 7

6 6 6 6 6

Sample Output

3

0

Limits

  • 对于20%的数据,\(1 \leq n \leq 100\)
  • 对于80%的数据,\(1 \leq n \leq 5000\)
  • 对于100%的数据, \(1 \leq T \leq 10 \),\(1 \leq n \leq 100000 \),\( 1 \leq m \leq 5000 \)

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/18.
//
// 前n项和 同余

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

static const auto _____ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

using ll=long long;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<int> mods(m + 1);
        mods[0] = 1;
        int currentMod = 0;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            currentMod = (currentMod + tmp) % m;
            ++mods[currentMod];
        }

        int ans = 0;
        for (int mod:mods) {
            if (mod <= 1) continue;
            else ans += mod * (mod - 1) / 2;
        }
        cout << ans << endl;
    }
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

int mods_cnt[5009] = { 0 };

int main() {
    int T;
    scanf("%d", &T);

    for (; T > 0; --T) {
        int n, m;
        scanf("%d %d", &n, &m);
        //初始化   
        memset(mods_cnt, 0, sizeof(int) * m);
        mods_cnt[0] = 1;
        long long ans = 0;
        for (int i = 0, cur_ans = 0; i < n; ++i) {
            int temp;
            scanf("%d", &temp);
            cur_ans = (cur_ans + temp) % m;
            ans += (long long)mods_cnt[cur_ans];
            ++mods_cnt[cur_ans];
        }
        printf("%lld\n", ans);
    }

    return 0;
}

skyzh's solution

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int S[10000];

int main() {
    int T;
    int m, n;
    int c = 0;
    long long res = 0;
    int tmp;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        memset(S, 0, sizeof(S));
        res = 0;
        c = 0;
        scanf("%d%d", &n, &m);
        for (int j = 0; j < n; j++) {
            scanf("%d", &tmp);
            c = (c + tmp) % m;
            ++S[c];
        }
        for (int j = 0; j < m; j++) {
            if (S[j] != 0) res += (long long) S[j] * (S[j] - 1) / 2;
        }
        res += S[0];
        cout << res << endl;
    }
    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t,sum,m,n,x[5000],tmp;
long long ans;
int main() {
    scanf("%d",&t);
    for (int i=0;i<t;++i){
        ans=0;
        sum=0;
        scanf("%d%d",&n,&m);
        memset(x,0,sizeof(x));
        x[0]=1;
        for (int j=0;j<n;++j){
            scanf("%d",&tmp);
            sum+=tmp;
            sum%=m;
            ans+=x[sum];
            x[sum]++;
        }
        printf("%lld",ans);
    }
    return 0;
}

yyong119's solution

#include <cstdio>
#include <cstring>
#define MAX_N 100010
#define MAX_M 5005
using namespace std;
int T, n, m;
int num[MAX_M];
inline int read() {
    register char ch = getchar(); register int res = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res;
}

int main() {
    register long long ans;
    register int cur;
    T = read();
    while (T--) {
        memset(num, 0, sizeof(num));
        ans = 0; cur = 0;
        n = read(), m = read();
        for (register int i = 0; i < n; ++i) {
            cur = (cur + read()) % m;
            ++num[cur];
        }
        for (register int i = 0; i < m; ++i)
                ans += num[i] * (num[i] - 1) >> 1;
        ans += num[0];
        printf("%lld\n", ans);
    }
}