洛谷P3941入阵曲

　　题目传送门

　　这道题也是今年湖南集训队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[];

inline ll read()

{

  char ch=getchar();ll num=;bool flag=false;

  while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}
//这里要注意要用while，一开始我用if被卡了四个点，非常玄学，可能是输入数据有毒;

  while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}

  return flag?-num:num;

}

int main()

{

  //freopen("water.in","r",stdin);

  n=read();m=read();mod=read();

  for(int i=;i<=n;i++)

    for(int j=;j<=m;j++){

      a[i][j]=read();

      sum[i][j]=(sum[i-][j]+sum[i][j-]-sum[i-][j-]+a[i][j]);

      if(sum[i][j]>=mod)sum[i][j]-=mod;}

//这里是一个小技巧，当sum已经大于mod时直接减去，可以缩小操作时的数据范围，对结果不影响，可以达到优化的效果;

  for(int i=;i<n;++i){

    for(int j=i+;j<=n;++j){

      cnt[]=;//别忘了初始化;

      for(int k=;k<=m;++k){

    b[k]=(sum[j][k]-sum[i][k])%mod;

//这里自己好好理解下，为什么这么做可行;

　　if(b[k]<)b[k]+=mod;

    ans+=cnt[b[k]];

    ++cnt[b[k]];

      }

      for(int k=;k<=m;++k)cnt[b[k]]=;

//每次做完以后还原数组;

    }

  }

  printf("%lld\n",ans);

  return ;

}

　　最后再放上炒鸡好听的入阵曲～～为我五团疯狂打call！！！！！