2644. 数列 (Standard IO)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[1000005]={0},t; //a为桶排序数组 
int main(){
    std::ios::sync_with_stdio(0);//读入输出加速 
    cin>>t;//测试数据的个数 
    while(t--){
        long long k,n; //k为模，n为数列的长度 
        cin>>k>>n; //输入 
        memset(a,0,sizeof(a)); //清空a数组 
        long long sum=0; //sum表示前缀和的累加mod K的结果 
        long long x;//x表示当前输入的数 
        long long ans=0; //ans表示结果 
        for(int i=1;i<=n;i++){ //循环表示当前读到的数列元素的位置 
            cin>>x; //输入该元素x 
            sum=(sum+x)%k; //累计前缀和并覆盖sum  
            a[sum%k]++; //桶排序，表示有多少同余的数 
        }
        for(int i=0;i<k;i++){ //循环访问排序结果 
            ans+=a[i]*(a[i]-1)/2;// 如果这个余数i有很多个情况，因为里面保存的是1-？的和mod k。
            //a[i]中任意两个相减都代表前缀和相减，代表的是一个1-n的子区间，例如：1，2，3，4，因为必须上一个区间比减去的区间大才可以
            //进行相减操作所以只能从1开始减2，3，4.从2开始减3，4.类似地计算这类排列的情况为：n*（n-1）/2
            //这样的话可以计算出来合法的子序列的方案和。 
        }
        cout<<ans<<endl;//加上本来余数就是零的序列 
    }
}