題目

小b喜歡和為K的倍數的序列。

現在有一個長度為n的序列A，請問A有多少個非空連續子序列是小b喜歡的。

輸入

第一行輸入一個正整數n；
第二行輸入n個整數，表示A[i]，以空格隔開；
第三行輸入一個正整數K；
其中1≤n≤30000，對于任意A[i]有-10000≤A[i]≤10000，2≤K≤10000

輸出

輸出一個數，表示子序列的數目

輸入樣例

6
4 5 0 -2 -3 1
5

輸出樣例

7

思路：實質要求有多少個連續區間和是 k 的倍數

考慮維護一個前綴和，由于數據范圍問題，在求前綴和的過程中直接對 sum[i] 取模 k，由于求的是多少個連續區間和是 k 的倍數的個數，因此并不影響最終答案

在求出前綴和后，首先枚舉終點，然后枚舉長度，進行判斷即可

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 40000+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std;int a[N]; int sum[N]; int main() {int n,k;scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%d",&a[i]); // sum[i]=a[i]+sum[i-1];}scanf("%d",&k);for(int i=1;i<=n;i++)sum[i]=(a[i]+sum[i-1])%k;int cnt=0;for(int i=1; i<=n; i++)//枚舉終點for(int j=1;j<=i;j++)//枚舉長度if((sum[i]-sum[j-1])%k==0)cnt++;printf("%d\n",cnt);return 0; }

?

總結

以上是生活随笔為你收集整理的和为k的倍数（51Nod-2522）的全部內容，希望文章能夠幫你解決所遇到的問題。

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