Submission #3245984

---

Source Code Expand

//ABC105

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<string>
#include<algorithm>

#define rep(i, a) for (int i = 0; i < a; i++)
#define reps(i, s, a) for (int i = s; i < a; i++)
#define llint long long int
using namespace std;

const int N_MAX = 100005;
const llint INF = 999999999999999;

int main()
{
    int n;
    llint m, a[N_MAX];
    map<llint, int> rem;
    vector<llint> key, sum;

    cin >> n >> m;

    sum.push_back(0);
    rem[0]++;
    key.push_back(0);

    rep(i, n) {
        cin >> a[i];
        sum.push_back(sum.back() + a[i]);

        llint r = sum.back() % m;
        rem[r]++;
        key.push_back(r);
    }
    sort(key.begin(), key.end());

    llint flg = -1, ans = 0;
    rep(i, key.size()) {
        if (rem[key[i]] >= 2 && key[i] != flg) ans += rem[key[i]] * (rem[key[i]] - 1) / 2;
        flg = key[i];
        //cout << ans << endl;
    }

    //cout << endl;
    //rep(i, key.size()) cout << key[i] << endl;

    cout << ans << endl;

}

Submission Info

Judge Result