蓝桥练习题-K倍区间

16.k倍区间 - 蓝桥云课 (lanqiao.cn)

首先，看到这个题，想到暴力求解，但显然，数据过大，暴力法过不了；

然后看到了一个办法：

对所有元素的前缀和取K的模，若s [i] ,s [j] 相同，则在j-1到i的区间内，区间和为K的倍数。

C++代码：

#include <iostream>
#include<queue>
using namespace std;
typedef long long ll;
ll A[100005];
ll N,K;
ll s[100005];//存放前缀和
ll count[100005];//计算前缀和的模相同的个数
ll ans=0;
int main()
{
  // 请在此输入您的代码
  cin>>N>>K;
  count[0]=1;
  for(int i=1;i<=N;i++){
    cin>>A[i];
    s[i]=s[i-1]+A[i];
    ans+=count[s[i]%K];//若有与s[i]%K相同的元素则相加
    count[s[i]%K]++;//模拟组合数
  }

  cout<<ans;
  return 0;
}

这其中有两句代码开始想了半天没有想明白，但自己动手模拟了一下后就豁然开朗了（这里建议大家多动手，不要只用脑子空想）

ans+=count[s[i]%K];//若有与s[i]%K相同的元素则相加
    count[s[i]%K]++;//模拟组合数

就是这两句，对此，我想到了两种解释方法：

1.模拟组合数

什么意思呢?大家先看下面一张表

现在假设我们i等于7时，count [1] ==4，但是ans是先加了count [1]之后再加加的；也就是ans最后一次加的是3，把前面所有关于count [1]的全部加起来，1+2+3=6；这是通过代数得来的，通过count [1] ，ans+=6；但我们仔细想一下四个相同的点，拿两个出来组成区间，这不就相当于组合数C2/4=6（2在上，4在下）吗？这么一想有没有一种豁然开朗的感觉！！！

2.与前面的配对

这个就比较好想到了，每产生一个新的s[i]%K都要与前面的所有相同的s[i]%K构成一次区间，若前面没有与之相同的元素，则加0；

以上就是这篇文章的全部内容了，希望对大家有所帮助！如有不懂的可以到评论区提出你的想法，大家一起讨论。