这道题也是今年湖南集训队Day8的第一题，昨天洛谷的公开赛上又考了一遍，来发个记录（其实是因为五月天，另外两道题分别是将军令和星空，出这次题目的人肯定同为五迷(✪㉨✪)）
话不多说。先理解下题意，给定一个n*m的矩阵，要求出能被k整除的子矩阵个数。
题意很简单，但是矩阵这方面的题目一直是我最大的软肋，所以昨天做的时候就直接交了个O( n^2 m^2 )的暴力，然后运气还可以，水了60分（据说暴力只有55？）然后在网上看到某集训队大犇的解题报告，搞懂了这题的正解做法。
那位大犇的做法是O( n^2 m )的，用读优可以卡过去，虽然我也想能不能还优化一下，但是无奈蒟蒻怎能比肩大犇QAQ
为了优化时间复杂度，在读入的时候就用一个二维数组记录下前缀和（用融斥原理），之后n^2枚举纵列起点和终点，然后枚举横列，用两个数组计数，当然其中也还有一些非常玄学的做法，具体还是看代码吧，在代码里解释：
#include<bits/stdc++.h> #define ll long long//切记要开long long; #define maxn 405 using namespace std; ll n,m,mod,a[maxn][maxn]; ll sum[maxn][maxn],ans; ll b[maxn],cnt[1000010]; inline ll read() { char ch=getchar();ll num=0;bool flag=false; while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();}
//这里要注意要用while，一开始我用if被卡了四个点，非常玄学，可能是输入数据有毒; while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();} return flag?-num:num; } int main() { //freopen("water.in","r",stdin); n=read();m=read();mod=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ a[i][j]=read(); sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]); if(sum[i][j]>=mod)sum[i][j]-=mod;} //这里是一个小技巧，当sum已经大于mod时直接减去，可以缩小操作时的数据范围，对结果不影响，可以达到优化的效果; for(int i=0;i<n;++i){ for(int j=i+1;j<=n;++j){ cnt[0]=1;//别忘了初始化; for(int k=1;k<=m;++k){ b[k]=(sum[j][k]-sum[i][k])%mod; //这里自己好好理解下，为什么这么做可行; if(b[k]<0)b[k]+=mod; ans+=cnt[b[k]]; ++cnt[b[k]]; } for(int k=1;k<=m;++k)cnt[b[k]]=0; //每次做完以后还原数组; } } printf("%lld ",ans); return 0; }
最后再放上炒鸡好听的入阵曲～～为我五团疯狂打call！！！！！