「fstqwq的2017/10/08模拟题」入阵曲 - Hash | Bill Yang's Blog
0%

「fstqwq的2017/10/08模拟题」入阵曲 - Hash

题目大意





题目分析

最大子矩阵经典套路:
枚举上边界$i$,枚举下边界$j$,将$i\rightarrow j$压缩成一行作前缀和。

然后从左到右记录一个前缀和的$Hash$,每次统计$Hash$中当前前缀和的数目计入答案。


代码

注:本题严重卡常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
namespace FastIO {
const int L=1<<15;
char buf[L],*S,*T;
char getchar() {
if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
return *S++;
}
int Get_Int(){
int res=0,bj=1;char c=getchar();
while(!isdigit(c)){if(c=='-')bj=-1;c=getchar();}
while(isdigit(c)){res=res*10+c-'0';c=getchar();}
return res*bj;
}
}
using FastIO::Get_Int;
const int maxn=405;
int n,m,k,a[maxn][maxn],Up[maxn][maxn],sum[maxn],Hash[1000005];
long long ans=0;
inline int Add(int x,int y) {
int tmp=x+y;
if(tmp>=k)tmp-=k;
if(tmp<0)tmp+=k;
return tmp;
}
int main() {
n=Get_Int();
m=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
a[i][j]=Get_Int();
Up[i][j]=(Up[i-1][j]+a[i][j])%k;
}
for(int i=1; i<=n; i++)
for(int j=i; j<=n; j++) {
Hash[0]++;
for(int x=1; x<=m; x++) {
int tmp=Add(sum[x-1],Up[j][x]);
sum[x]=Add(tmp,-Up[i-1][x]);
ans+=Hash[sum[x]];
Hash[sum[x]]++;
}
Hash[0]--;
for(int x=1; x<=m; x++)Hash[sum[x]]--;
}
printf("%lld\n",ans);
return 0;
}


特别声明

本题解已获得$fstqwq$授权,原作者使用CC BY-NC-ND 4.0协议进行共享。
转载本套题请联系$fstqwq(QQ:849199382)$。

姥爷们赏瓶冰阔落吧~