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;//加上本来余数就是零的序列 
    }
}

 

上一篇:3403. 题解【NOIP2013模拟】数列变换 (Standard IO)


下一篇:实现透明不透并且和原standard shader效果一样但没有阴影而且可以在手机端用刚才发现一个bug就是在电脑端看使用这个shader的会有金属光泽来回变