P3941 入阵曲

2018-11-01 16:32:45


题意:计算给定矩阵中有多少子矩形满足其中数字之和是 $k$ 的倍数


最暴力的想法就是直接用二维前缀和 $n^4$ 枚举

发现这样会有很多重复且不必要的计算

考虑优化

可以发现,如果 $sum[l-1]\%k=sum[r]\%k$ ,那么 $[l,r]$ 的区间和是 $k$ 的倍数

那么可以把多行压成一行,从上到下扫前缀和

记录每个余数出现的次数 $cnt$ ,每次统计贡献并累加

这样就只需要 $O(n^2m)$ 的复杂度了

注意初始 $cnt[0]=1$ ,每次枚举之后要把改变过的数值设为 $0$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=405,M=1e6+5;
int n,m,k,cnt[M],val[N];
ll sum[N][N],ans;
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
int main()
{
    n=read(),m=read(),k=read();
    for (int i=1;i<=n;i++)
      for (int j=1;j<=m;j++)
        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+read();
    for (int i=0;i<n;i++)
      for (int j=i+1;j<=n;j++)
      {
          cnt[0]=1;
          for (int t=1;t<=m;t++)
          {
              val[t]=(sum[j][t]-sum[i][t])%k;
              ans+=cnt[val[t]]; ++cnt[val[t]];
          }
          for (int t=1;t<=m;t++) cnt[val[t]]=0;
      }
    printf("%lld\n",ans);
    return 0;
}