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

你能求出數(shù)列中總共有多少個(gè)K倍區(qū)間嗎？

輸入
第一行包含兩個(gè)整數(shù)N和K。(1 <= N, K <= 100000)
以下N行每行包含一個(gè)整數(shù)Ai。(1 <= Ai <= 100000)

輸出
輸出一個(gè)整數(shù)，代表K倍區(qū)間的數(shù)目。

例如，
輸入：
5 2
1
2
3
4
5

程序應(yīng)該輸出：
6

資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 < 2000ms

通過前綴和加取模，

然后要知道一個(gè)東西就是，只要前綴出現(xiàn)同樣的就得累加，

也就是一個(gè)累計(jì)數(shù)組。

而且累計(jì)數(shù)組考慮的不包括本身，所以最后要吧取摸為零的加進(jìn)去。

?

1 #include <iostream> 2 #define N 100000 3 #define ll long long int 4 using namespace std; 5 ll an[N], bn[N]; 6 int n, k; 7 8 int main(){ 9 cin >> n >> k; 10 for(int i = 1; i <= n; i++ ){ 11 cin >> an[i]; 12 an[i] %= k; 13 } 14 for(int i = 1; i <= n; i++){ 15 an[i] = (an[i] + an[i-1])%k; 16 } 17 ll sum = 0; 18 for(int i = 1; i <= n; i++){ 19 sum += (bn[an[i]]++); 20 } 21 cout << sum + bn[0] << endl; 22 return 0; 23 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zllwxm123/p/10578428.html

總結(jié)

以上是生活随笔為你收集整理的k倍区间的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。