蓝桥杯试题 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
样例输出
6
 
思路:我们首先要我们是要求出任意长度的区间和 符合是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[]={,,,,,,,,,,,,};

int dir[][]={, ,, ,-, ,,-};

int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};

const int inf=0x3f3f3f3f;

const ll mod=1e9+;

int n,k;

int a[];

int sum[];

int dp[];

int main(){

//    ios::sync_with_stdio(false);

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

    ll ans=;

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

        scanf("%d",&a[i]);

        sum[i]=(sum[i-]+a[i])%k; //求前缀和对k求余

        if(sum[i]==){ //自己也是k倍区间

            ++dp[sum[i]];

            ans+=(dp[sum[i]]);

        }

        else{    //和前面余数相同的点组成k倍区间

            ans+=(dp[sum[i]]);

            ++dp[sum[i]];

        }

    }

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

    return ;

}

蓝桥杯试题 k倍区间(dp)的相关教程结束。