Source Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define sp ' '
#define assert(x,a) if(x){cout << a << endl;return;}
#define sortv(x)sort(x.begin(),x.end())
#define revev(x)reverse(x.begin(),x.end())
inline void fast(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    }
vector<vector<int>>graph;

vector<bool>vis(100001,false);
bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}
inline void answer(int c){assert(c==0,"NO")cout << "YES" << endl;}
void solve()
{
    ll ans1 = 0;
    int a,b;cin >>a >> b;
    vector<ll>l(a + 1);
    map<ll,int>ans;
    l[0] = 0;
    for(int i = 1;i <= a;i++)
    {
        ll w;cin >> w;
        l[i] = w + l[i - 1];
        ans[l[i] % b]++;
    }
    ll prefix = 0;
    for(int i =l.size();i >=1;i--)
    {
        if(ans[l[i] % b] > 0)
            ans[l[i] % b]--;
        ll temp = l[i] - l[i - 1];
        prefix+=temp;
        ans1+=ans[(b - (prefix % b)) % b];
    }
    cout << ans1 << endl;
}
int main()
{
    fast();
    ll t{ 1 };cin >> t;
  // cin.ignore();
    while (t--)
    {
        solve();
    }
}
Copy
Number of Ways iwjx
GNU G++17
1 ms
184 KB
Wrong Answer