ABC146E Rem of Sum is Num

---

一道巧妙的思维题，考验了对数学式的转化

---

题意:

给出一个数列和常数k，求合法子序列的个数

其中合法子序列需要满足：

$$\sum_{i}^{j}{a_i} \equiv j-i+1\ \left (\mod k \right )$$

---

题解：

比赛时毫无思路，赛后看了题解茅塞顿开

让我们来转化这个需要满足的式子，其中规定$s_i$表示1-i的前缀和：

$$\sum_{i}^{j}{a_i} \equiv j-i+1 \ (\mod k )$$ $$s_j - s_{i-1} \equiv j-(i-1) \ (\mod k )$$ $$s_j - s_i \equiv j-i \ (\mod k )$$ $$s_i-i = s_j-j \ (j-i<k )$$

也就是说，只要找到一组i,j满足上述式子，ans就能+1

显然的，$s_i-i$可以放到一个map里，为了满足其$j-i<k$的要求，可以对于每个map开一个queue

于是得到了标算：从左到右扫一遍，检索并维护对于当前的$s_i-i$有几个与它相等且合法

要注意的是，需要先在map[0]里塞个下标0，为了保证从1到i是合法的情况

---

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#include <tr1/unordered_map>

const int N=2e5+5;
int n,k,s[N];
long long ans;
tr1::unordered_map<int,queue<int> > mp;

signed main(){
    read(n);read(k);
    for(int i=1,x;i<=n;i++){
        read(x);
        x%=k;
        s[i]=(s[i-1]+x)%k; //前缀和
    }
    mp[0].push(0); //塞个0
    for(int i=1;i<=n;i++){
        int now=s[i]-i;
        now=(now%k+k)%k;
        while(!mp[now].empty()&&i-mp[now].front()>=k) mp[now].pop(); //维护队列
        ans+=mp[now].size(); //累加之前有几个合法
        mp[now].push(i);
    }
    write(ans);
}