F – Subarrays题解

F – Subarrays

题意：给你一个序列，问这个序列里有多少个子串的和能被k整除。
思路：求前缀和，然后每个位置对k取模，模数相等的位置之间，是一个满足条件的字串。
因为求的是前缀和，所以取模后相等，做差刚好去掉这个模后结果。
某个位置前面有多少个取模和该位置取模相等的数，用map记录一下。
特别注意，要对mp进行初始化！

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, k, ans, res;
map<int,int> mp;

signed main()
{
    cin >> n >> k;
    mp[0] = 1;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        ans += x;
        ans = ans % k;
        res +=  mp[ans];
        mp[ans] ++;
    }
    cout << res << endl;
    return 0;
}

原文地址：http://www.cnblogs.com/N-lim/p/16906980.html