ACM选修HUST1058(市赛题) Lucky Sequence 同余定理

Description

Edward 得到了一个长度为 N 的整数序列，他想找出这里面有多少个“幸运的”
连续子序列。一个连续子序列被称为“幸运的”，当且仅当该子序列内的整数之
和恰好是 K 的整数倍数。他请求你写一个程序来计算他喜欢的连续子序列个数.

Input

输入第一行是一个整数 T，表示有 T 组数据。
每组数据第一行是两个整数 N (1 <= N <= 10^6), K (1 <= K <= 10^9)。
接下来的一行包含 N 个整数 Ai (|Ai| <= 10^9)。

Output

对于每组测试数据，输出一行仅包含一个整数，表示 Edward 喜欢的连续子序
列数量。

Sample Input

2

5 3

1 2 3 4 1

6 2

1 2 1 2 1 2

Sample Output

4

9

HINT

一开始没有想到同余定理，根据nanako大神的说法，可以差不多刚好卡时间和内存AC，但是鶸并不会..

记得当时模拟赛后，nanako对这题的脑洞已经几乎完全接近正解了。

分析：根据同余定理：(a-b)%c=a%c-b%c，可以想到使用前缀和，并记录每个前缀和的模k后的值，O（n^2）的解法是两层循环前缀数组模k套公式，显然超时（好蠢，再找到有几个相同余数的数。例如样例二：前缀和并模K后的数组为1 1 0 0 1 1 ，找到余数相同的 b[0],b[1],b[4],b[5]，4个,那么在其中取首尾，不同位置的组合有（3+1）*（3）/2=6，同样的，零有2个，但要注意余数为0的话意味着该位置的前缀和本身就是K的倍数，所以0的组合为 (2+1)*2/2=3。

注意点：给出的数有可能是负数，故求余数时需要变换。

*更新点：因为我的写法是没有先计算前缀和而直接计算模后数组的，所以注意求模后的数组时，加上前一个值后就要模k再判断是否小于0进行变换。

 #include <stdio.h>

 #include <iostream>

 #include <string.h>

 #include <algorithm>

 #define ll long long

 using namespace std;

 int a[], b[];

 ll Xe(ll a)

 {

     return ((a+)*(a))/;

 }

 int main()

 {

     int T, t;

     int n, k;

     ll  x, ans;

     scanf("%d", &T);

         while(T--)

         {

             scanf("%d%d", &n, &k);

             ans=;

             scanf("%d",&b[]);

             b[]%=k;      //注意先模再判

             if(b[] < )

                 b[]=(b[]+k)%k;

             for(int i=; i<n; i++)

             {

                 scanf("%d",&t);

                 b[i]=b[i-]+t;

                 b[i]%=k;   //注意先模

                 if(b[i]<)

                     b[i]=(b[i]+k)%k;

             }

             sort(b, b+n);

             b[n]=-;

             /*for(int i=1; i<=n; i++)

             {

                 cout<<b[i]<" ";

             }

             for(int i = 1; i <= n; i++)

             {

                 for(int j = 0; j < i; j++)

                 {

                     if(!((k+b[i]%k-b[j]%k)%k))

                     {

                         ans++;

                         //printf("%d~%d\n",i,j );

                     }

                 }

             }*/

             x=;

             for(int i = ; i <= n; i++)

             {

                 if(b[i]==b[i-])

                     x++;

                 else

                 {

                     if(b[i-]!=)

                         x--;

                     ans+=Xe(x);

                     x=;

                 }

             }

             printf("%lld\n", ans);

         }

 }

巴特西