1907: k倍區間Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?40??Solved:?19
[Submit][Status][Web Board]

Description

給定一個長度為N的數列，A1, A2, ... AN，如果其中一段連續的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍數，我們就稱這個區間[i, j]是K倍區間。

你能求出數列中總共有多少個K倍區間嗎？

Input

每個數據包含多組輸入數據

第一行包含兩個整數N和K。(1 <= N, K <= 100000)?
以下N行每行包含一個整數Ai。(1 <= Ai <= 100000)

Output

輸出一個整數，代表K倍區間的數目。

Sample Input

5 21 2 3 4 5

Sample Output

6

解析：直接暴力n^2，超時，所以要應用另外一種做法--前綴和。

分析:?
統計前綴和?
sum[1] = a1;?
sum[2] = a1+a2;?
sum[i] = a1+a2+…+ai;?
對于任意一段區間[l,r]的和就是sum[r]-sum[l-1].?
(sum[r]-sum[l-1])%k 保證了[l,r]這段區間要么%k等于0 要么比k小 等于0這表示了正好是k的倍數 然后通過前綴和相同的數據來判斷出剩下的k的倍數:(sum[r]-sum[l-1])%k == 0.變形后就是：sum[r]%k==sum[l-1]%k .

程序分析樣例:?
輸入: 1 2 3 4 5?

%k后前綴和: 1 1 0 0 1

當i = 0, sum=0,bk[1]=1;
當i = 1, sum=1,bk[1]=2; //因為當bk[1]之前為1時 可得相減1-1=0為k的倍數
當i = 2, sum=1,bk[0]=1;
當i = 3, sum=2,bk[0]=2; //同上理,當0-0時還是0
當i = 4, sum=4,bk[1]=3; //之前bk[1]有2個? 所以有2種-法 所以sum加上2
最后統計bk[0]有幾個 sum+=bk[0]? //因為之前只考慮了相減的情況 沒有考慮到本身

sum = 6;

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<vector> #include<map> #include<list> #include<algorithm> #define SIZE 200000+5 using namespace std;const int maxn=100000+5; int a[maxn],cnt[maxn];int main() {int n,k;while(~scanf("%d%d",&n,&k)){memset(a,0,sizeof(a));memset(cnt,0,sizeof(cnt));int sum=0;for(int i=1; i<=n; i++){int t;scanf("%d",&t);a[i]=(a[i-1]+t)%k;sum+=cnt[a[i]]++;}printf("%d\n",sum+cnt[0]);}return 0; }

總結

以上是生活随笔為你收集整理的zcmu-1907的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。