蓝桥杯试题 k倍区间(dp)

问题描述

　　给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。

　　你能求出数列中总共有多少个K倍区间吗？

输入格式

　　第一行包含两个整数N和K。(1 <= N, K <= 100000)
　　以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

输出格式

　　输出一个整数，代表K倍区间的数目。

样例输入

5 2
1
2
3
4
5

样例输出

思路:我们首先要我们是要求出任意长度的区间和符合是k的倍数的区间个数这样我们很容易得到 (sum[i]-sum[j])%k==0

接着我们可以得到 (sum[i]%k-sum[j]%k)%k==0 因为前缀和都为正整数所以我们可以推导出 sum[i]%k==sum[j]%k

所以我们只需要找到前缀和对k求余结果相同的两个点他们之间的区间即为k倍区间

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define ll long long int
using namespace std;
//inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
//inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1};
int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
int n,k;
int a[100007];
int sum[100007];
int dp[100007];
int main(){
//    ios::sync_with_stdio(false);
    scanf("%d%d",&n,&k);
    ll ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i]=(sum[i-1]+a[i])%k; //求前缀和对k求余 
        if(sum[i]==0){ //自己也是k倍区间 
            ++dp[sum[i]];
            ans+=(dp[sum[i]]);
        }
        else{    //和前面余数相同的点组成k倍区间 
            ans+=(dp[sum[i]]);
            ++dp[sum[i]];
        }
    }
    printf("%lld
",ans);
    return 0;
}