luogu3941入阵曲

搜索

题面

统计在给出的$n*m$矩阵中，有多少个不同的子矩形中的数字之和是$k$的倍数？

解析

切不掉这道题是我傻逼
显然预处理出每列的前缀和。
然后枚举矩形的上界和下界，统计下范围内哪些列余数相等就行。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=500,M=1e6+100;
int n,m,k,mx=1e6,tag=1,s[N][N],t[M];
ll ans;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();m=gi();k=gi();
  fp(i,1,n)
    fp(j,1,m)
    s[i][j]=(gi()+s[i-1][j]+s[i][j-1]-s[i-1][j-1]+k)%k;
  fp(i,1,n)
    fp(j,i,n)
    {
      fp(l,0,m) ++t[(s[j][l]-s[i-1][l]+k)%k];
      fp(l,0,m) --t[(s[j][l]-s[i-1][l]+k)%k],ans+=t[(s[j][l]-s[i-1][l]+k)%k];
    }
  printf("%lld\n",ans);
  return 0;
}