P3941 入阵曲

题意：计算给定矩阵中有多少子矩形满足其中数字之和是$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; } ```