题意是这样的 给定一个n*m的整数矩阵 n和m均小于1000
对这个矩阵删去任意行和列后剩余一个矩阵为M{x1,x2,,,,xm;y1,y2,,,,,yn}表示删除任意的M行N列
对于这个剩下的矩阵，我们考虑其中是否存在特殊的元素，保证这些元素是所在行最大，所在列最小的元素 且非之一。
求对于所有删法，上述元素个数之和 对10^9+7取余。
显然所有删法 有2^(n+m)种 暴力是搞不定的。
于是反过来看，矩阵的元素最多有10^6个 是不是可以考虑每一个元素对最终答案的贡献？
所谓贡献，就是它在哪几种删法的矩阵中是“特殊的元素”。
于是，我们考虑对于任意一个元素，在它所在的行有多少严格小于它的，在它所在的列有多少严格大于它的 然后乘法原理一下，就可以知道这个元素对答案的贡献是多少了。
没有想到好的预处理方法可以在常数时间内回答上述询问，于是考虑在遍历元素的过程中直接求得上述询问。
首先对所有元素排序，（当然提前标记好每个元素所在行和所在列）
这样当我们遍历到其中某个元素时，根据之前遍历过的元素以及元素总和，知道所在行列的具体情况了，然后对2的1000次幂提前打表储存，最后的复杂度为O(N*M) 顺利AC
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1000+1;
typedef long long int LL;
struct point
{
LL val;
int x;int y;
};
point pp[maxn*maxn];
int sumr[maxn],sumc[maxn];
int sumlr[maxn],sumlc[maxn],sumrr[maxn],sumrc[maxn];
const LL MOD=1000000007;
bool cmp(point a,point b)
{
return a.val<b.val;
}
queue<point>q,qq;
LL poww[maxn+10];
int main()
{//freopen("t.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
LL np=1;
for(int i=0;i<=1005;i++)
{
poww[i]=np;
np=np*2%MOD;
}
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
scanf("%lld",&pp[i*m+j].val);
pp[i*m+j].x=i;pp[i*m+j].y=j;
}
for(int i=0;i<n;i++)sumr[i]=sumlr[i]=sumrr[i]=m;
for(int i=0;i<m;i++)sumc[i]=sumlc[i]=sumrc[i]=n;
sort(pp,pp+n*m,cmp);
LL nv=pp[0].val;
int suma=0,sumb=0;
LL ans=0;
int i=0;
while(i<n*m)
{
while(pp[i].val==nv&&i<n*m)
{
// cout<<pp[i].val<<endl;
q.push(pp[i]);
sumrr[pp[i].x]--;
sumrc[pp[i].y]--;
i++;
}
while(!q.empty())
{
point np=q.front();q.pop();
//cout<<"npv "<<np.val<<"x"<<np.x<<endl;
qq.push(np);
//cout<<"sumc"<<sumc[np.y]<<endl;
//cout<<"sumlc"<<sumc[np.y]-sumlc[np.y]<<endl;
//cout<<"sumr"<<sumrr[pp[i].x]<<endl;
ans=(ans+poww[sumc[np.y]-sumlc[np.y]]*poww[sumrr[np.x]])%MOD;
//cout<<"ans:"<<ans<<endl;
}
nv=pp[i].val;
while(!qq.empty())
{
point np=qq.front();qq.pop();
sumlc[np.y]=sumrc[np.y];
}
}
printf("%lld
",ans);
}
return 0;
}
————————————————
吐槽一下ZJU校赛，竟然 竟然有三道水题！！！
我做完两道估计就没有水题了，于是花了一个小时写这道计数题，回头看还有一道日历的水题，时间不够调不出来了。。。卒 还好顺利晋级省赛，希望和新的队友密切配合拿下省赛。