传送门
problem
对于一个由非负整数构成的矩阵
A
n
A_n
An，定义矩阵的
AND
\texttt{AND}
AND 值为矩阵中所有数二进制
AND(&)
\texttt{AND(\&)}
AND(&) 的运算结果；定义矩阵的
OR
\texttt{OR}
OR 值为矩阵中所有数二进制
OR(|)
\texttt{OR(|)}
OR(|) 的运算结果。
给定一个
n
×
n
n\times n
n×n 的矩阵，请求出：
该矩阵的所有子矩阵的
AND
\texttt{AND}
AND 值之和（所有子矩阵
AND
\texttt{AND}
AND 值相加的结果）。该矩阵的所有子矩阵的
OR
\texttt{OR}
OR 值之和（所有子矩阵
OR
\texttt{OR}
OR 值相加的结果）。
答案对
1
0
9
+
7
10^9+7
109+7 取模。
数据范围：
1
≤
n
≤
1000
1\le n\le 1000
1≤n≤1000，
A
i
j
<
2
31
A_{ij}< 2^{31}
Aij<231。
solution
蛮简单的一道题。
首先还是按位处理，把问题转换成，求一个
01
01
01 矩阵中全为
1
1
1 的子矩阵数量以及至少有一个
1
1
1 的子矩阵数量。
第一个可以用单调栈做，如果不会可以先做仓鼠窝这道题。
对于第二个，由于子矩阵的总数是
(
n
(
n
+
1
)
2
)
2
(\frac{n(n+1)}2)^2
(2n(n+1))2，所以我们可以反转后算全为
1
1
1 的子矩阵数量。
为什么
n
×
n
n\times n
n×n 的矩阵的子矩阵总数是
(
n
(
n
+
1
)
2
)
2
(\frac{n(n+1)}2)^2
(2n(n+1))2 呢？ 把矩阵看成网格图，那么有
n
+
1
n+1
n+1 条竖线和
n
+
1
n+1
n+1 条横线。而一个子矩阵相当于是两条竖线和两条横线形成的，所以子矩阵数是
C
n
+
1
2
×
C
n
+
1
2
=
(
n
(
n
+
1
)
2
)
2
C_{n+1}^2\times C_{n+1}^2=(\frac{n(n+1)}2)^2
Cn+12×Cn+12=(2n(n+1))2。
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1005
#define P 1000000007
using namespace std
;
int n
,tot
,A
[N
][N
],a
[N
][N
],h
[N
],stk
[N
],num
[N
];
int add(int x
,int y
) {return x
+y
>=P
?x
+y
-P
:x
+y
;}
int dec(int x
,int y
) {return x
-y
< 0?x
-y
+P
:x
-y
;}
int mul(int x
,int y
) {return 1ll*x
*y
%P
;}
int calc(){
int ans
=0;
memset(h
,0,sizeof(h
));
for(int i
=1;i
<=n
;++i
){
int top
=0;
for(int j
=1;j
<=n
;++j
){
if(!a
[i
][j
]) h
[j
]=i
;
while(top
&&h
[stk
[top
]]<h
[j
]) top
--;
num
[top
+1]=add(num
[top
],mul(i
-h
[j
],j
-stk
[top
]));
stk
[++top
]=j
,ans
=add(ans
,num
[top
]);
}
}
return ans
;
}
int main(){
scanf("%d",&n
);
for(int i
=1;i
<=n
;++i
)
for(int j
=1;j
<=n
;++j
)
scanf("%d",&A
[i
][j
]);
int Xor
=0,Or
=0;
tot
=n
*(n
+1)/2,tot
=mul(tot
,tot
);
for(int k
=30;~k
;--k
){
for(int i
=1;i
<=n
;++i
)
for(int j
=1;j
<=n
;++j
)
a
[i
][j
]=(A
[i
][j
]>>k
)&1;
Xor
=add(Xor
,mul(calc(),1<<k
));
for(int i
=1;i
<=n
;++i
)
for(int j
=1;j
<=n
;++j
)
a
[i
][j
]=(!a
[i
][j
]);
Or
=add(Or
,mul(dec(tot
,calc()),1<<k
));
}
printf("%d %d\n",Xor
,Or
);
return 0;
}
