[Luogu3941]入阵曲

Posted on | In

一道难度适中的的小清新思维好题

我们先对原矩阵做一遍膜$K$意义下的前缀和

不难发现，膜$K$意义下前缀和相等的两个矩形

它们的前缀和的差一定是$K$的倍数

但是我们必须保证这两个矩形不重叠的部分一定是一个矩形

那么我们可以先枚举上下边界再枚举右边界

开一个桶依次记录膜$K$意义下的前缀和

最后根据每个数出现的次数计算贡献即可

特别要注意的是把桶清空的时候不能$memset$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
long long m,n,ans,mod;
long long a[404][404],b[404],c[1000001];
inline long long read() {
    char ch=getchar(); long long num=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch^'0'),ch=getchar();
    return num;
}
int main() {
    n=read(),m=read(),mod=read();
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            a[i][j]=read(),(a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+mod)%=mod;
    for(register int i=0;i<n;++i)
        for(register int j=i+1;j<=n;++j) {
            c[0]=1;
            for(register int k=1;k<=m;++k)
                b[k]=(a[j][k]-a[i][k]+mod)%mod,ans+=c[b[k]]++;
            for(register int k=1;k<=m;++k) c[b[k]]=0;
        }
    printf("%lld\n",ans);
    return 0;
}