http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5564
根据它的定义是行最小，列最大。
可以证明鞍点是唯一的。
单独考虑每一个元素的贡献，它能成为鞍点的情况有：
1、在这一行中，<= a[i][j]的元素肯定要删除，那么剩下k1个大于他a[i][j]的，当然a[i][j]本身不能删除
2、在这一列中，>= a[i][j]的元素肯定要删除，那么剩下k2个小于a[i][j]的，当然a[i][j]本身不能删除
那么，总情况就是，对于那k1个元素，对应着k1列，要么删除，要么不删除，有2^k1种情况，在k2个元素中，对应着k2列，也是要么删除，要么不删除，。有2^k2种情况，相乘就是贡献。
也就是要知道a[i][j]在当前行中，有多少个元素比它大，在当前列中，有多少个元素比它小，处理出来即可。
比赛的时候想到了bit，然后发现好像sort然后二分找即可。
越学越傻
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e6 + ;
int c[maxn];
int lowbit(int x) {
return x & (-x);
}
void upDate(int pos, int val) {
while (pos <= maxn - ) {
c[pos] += val;
pos += lowbit(pos);
}
}
int query(int pos) {
int ans = ;
while (pos) {
ans += c[pos];
pos -= lowbit(pos);
}
return ans;
}
int a[ + ][ + ];
int row[ + ][ + ], col[ + ][ + ];
const int MOD = 1e9 + ;
LL quick_pow(LL a, LL b, LL MOD) {
LL base = a % MOD;
LL ans = ;
while (b) {
if (b & ) {
ans = (ans * base) % MOD;
}
base = (base * base) % MOD;
b >>= ;
}
return ans;
}
void work() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
scanf("%d", &a[i][j]);
}
}
memset(c, , sizeof c);
for (int i = ; i <= n; ++i) {
if (i != ) {
for (int j = ; j <= m; ++j) {
upDate(a[i - ][j], -);
}
}
for (int j = ; j <= m; ++j) {
upDate(a[i][j], );
}
for (int j = ; j <= m; ++j) {
row[i][j] = m - query(a[i][j]);
}
}
memset(c, , sizeof c);
for (int i = ; i <= m; ++i) {
if (i != ) {
for (int j = ; j <= n; ++j) {
upDate(a[j][i - ], -);
}
}
for (int j = ; j <= n; ++j) {
upDate(a[j][i], );
}
for (int j = ; j <= n; ++j) {
col[j][i] = query(a[j][i] - );
}
}
LL ans = ;
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
// printf("[%d %d] ", row[i][j], col[i][j]);
ans += quick_pow(, row[i][j], MOD) * quick_pow(, col[i][j], MOD) % MOD;
if (ans >= MOD) ans %= MOD;
}
// cout << endl;
}
// cout << endl;
printf("%lld\n", ans);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
bit跑了990ms。。吓死了。