开始完全没思路
在洛谷看到样例一,突发奇想,决定先做一下元素只有0/1的情况
发现子任务1是全1子矩阵
子任务2是总子矩阵个数减去全0子矩阵
发现全0/1矩阵可以构造单调栈解决。具体做法:前缀和求出每个格子上面有多少颜色为0/1的格子(是0是1有求子任务1/2决定),然后发现可以每次在单调栈中找出相邻的两个值,算出内部区块的面积,多次累加后发现刚好是全0/1子矩阵的个数
小技巧:把单调队列的第0项的坐标置0,可以避免特判
让后求总子矩阵个数也很简单,递推解决(我数学不好,瑟瑟发抖)
公式: ff[i][j] = ff[i - 1][j] + ff[i][j - 1] - ff[i - 1][j - 1] + i * j;
那么总子矩阵个数即为f[n][n]
让后向元素任意值得矩阵迈进
发现恰好可以以二进制来展开获得0/1矩阵
代码:
for (register int i = 0; i < n; ++i)
for (register int j = 0; j < n; ++j)
a[i][j] = (atot[i][j] & (1 << flr)) ? 1 : 0;
atot为读入数组,a为需要的0/1数组
flr表示现在在二进制的flr位
让后算出来的答案乘以(1 << flr)累加到总答案上
打完以后发现30分
快速浏览代码没找到错误(我太菜了)
后来点开了题解,正准备浏jie览jian,突然发现有一处没有MOD,
MOD了以后果断(???)AC...
贴个代码
#include <cstdio>
#define ll long long const ll MOD = 1e9+; inline ll read(){
ll x = ; int zf = ; char ch = ' ';
while (ch != '-' && (ch < '' || ch > '')) ch = getchar();
if (ch == '-') zf = -, ch = getchar();
while (ch >= '' && ch <= '') x = x * + ch - '', ch = getchar(); return x * zf;
} ll atot[][];
int a[][];
int sum[][]; ll ff[][]; ll or_init; struct Node{
ll pos;
ll hei;
} ddstk[];
int top; int main(){
int n = read();
for (register int i = ; i < n; ++i)
for (register int j = ; j < n; ++j)
atot[i][j] = read();
for (register int i = ; i <= n; ++i){
for (register int j = ; j <= n; ++j){
ff[i][j] = ff[i - ][j] + ff[i][j - ] - ff[i - ][j - ] + i * j;
if (ff[i][j] < )
ff[i][j] += MOD;
ff[i][j] %= MOD;
}
}
or_init = ff[n][n];
ll ans1 = , cur_ans1, ans2 = , cur_ans2;
ddstk[].pos = ;
for (int flr = ; flr < ; ++flr){
for (register int i = ; i < n; ++i)
for (register int j = ; j < n; ++j)
a[i][j] = (atot[i][j] & ( << flr)) ? : ;
//getAnd
for (register int i = ; i < n; ++i)
for (register int j = ; j < n; ++j)
if (i != )
sum[i][j] = (a[i][j] == ) ? sum[i - ][j] + : ;
else
sum[i][j] = (a[i][j] == ) ? : ;
cur_ans1 = ;
for (register int i = ; i < n; ++i){
top = ;
for (register int k = ; k < n; ++k){
while (top){
if (sum[i][k] <= ddstk[top].hei)
--top;
else
break;
}
ddstk[++top].pos = k + ;
ddstk[top].hei = sum[i][k];
for (int l = top; l >= ; --l){
cur_ans1 += ddstk[l].hei * (ddstk[l].pos - ddstk[l - ].pos);
cur_ans1 %= MOD;
}
}
}
ans1 += (cur_ans1 * ((1ll << flr) % MOD)) % MOD;
ans1 %= MOD;
//getOr
for (register int i = ; i < n; ++i)
for (register int j = ; j < n; ++j)
if (i != )
sum[i][j] = (a[i][j] == ) ? sum[i - ][j] + : ;
else
sum[i][j] = (a[i][j] == ) ? : ;
cur_ans2 = ;
for (register int i = ; i < n; ++i){
top = ;
for (register int k = ; k < n; ++k){
while (top){
if (sum[i][k] <= ddstk[top].hei)
--top;
else
break;
}
ddstk[++top].pos = k + ;
ddstk[top].hei = sum[i][k];
for (int l = top; l >= ; --l){
cur_ans2 += ddstk[l].hei * (ddstk[l].pos - ddstk[l - ].pos);
cur_ans2 %= MOD;
}
}
}
cur_ans2 = (or_init - cur_ans2 + MOD) % MOD;
ans2 += (cur_ans2 * ((1ll << flr) % MOD)) % MOD;
ans2 %= MOD;
}
printf("%lld %lld", ans1, ans2);
return ;
}