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;}
struct class1{
    vector<int>indexes;
};
void solve()
{
    ll ans1 = 0;
        ll n, k; cin >> n >> k;
        vector<ll>l(n); for (ll& e : l)cin >> e;
        vector<ll>prefix_sum(n + 2);
        vector<ll>suffix_sum(n + 2);
        map<ll,class1>queries;
        prefix_sum[1] = l[0];
        for (ll i = 2; i <= l.size(); i++)
        {
            prefix_sum[i] = prefix_sum[i - 1] + l[i - 1];
        }
        reverse(l.begin(), l.end());
        suffix_sum[0] = 0;
        suffix_sum[1] = l[0];
        queries[suffix_sum[1] % k].indexes.push_back(l.size());
        for (ll i = 2; i <= l.size(); i++)
        {
            suffix_sum[i] = suffix_sum[i - 1] + l[i - 1];
            queries[suffix_sum[i] % k].indexes.push_back(l.size() - (i - 1));
        }
        for(int i = 1;i < prefix_sum.size()-1;i++)
        {
            ll ansq = prefix_sum[i] % k;
            if(ansq == 0)
            {
                    ll temp = lower_bound(queries[0].indexes.begin(),queries[0].indexes.end(),i,greater<int>()) -  queries[0].indexes.begin();
                    ans1+=abs(temp);
            }
            else
            {
                    ll temp = lower_bound(queries[abs(k-ansq)].indexes.begin(),queries[abs(k-ansq)].indexes.end(),i,greater<int>()) -  queries[abs(k-ansq)].indexes.begin();
                    ans1+=abs(temp);
            }
        }
    cout <<ans1 << endl;
}
int main()
{
    fast();
    ll t{ 1 };cin >> t;
  // cin.ignore();
    while (t--)
    {
        solve();
    }
}
Copy
Number of Ways iwjx
GNU G++17
912 ms
42.7 MB
Accepted