ZOJ 3955 Saddle Point

排序。

枚举每一个格子，计算这个格子在多少矩阵中是鞍点，只要计算这一行有多少数字比他大，这一列有多少数字比他小，方案数乘一下就是这个格子对答案做出的贡献。

#include<bits/stdc++.h>

using namespace std;

int n,m;

long long mod = 1e9+;

int a[][];

int num1[][];

int num2[][];

long long b[];

struct X

{

    int id,val;

}s[];

bool cmp1(X a,X b)

{

    return a.val<b.val;

}

bool cmp2(X a,X b)

{

    return a.val>b.val;

}

int main()

{

    b[]=;

    for(int i=;i<=;i++) b[i]=(b[i-]*)%mod;

    int T; scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        memset(num1,,sizeof num1);

        memset(num2,,sizeof num2);

        for(int i=;i<=n;i++) for(int j=;j<=m;j++) scanf("%d",&a[i][j]);

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=m;j++) s[j].id=j, s[j].val=a[i][j];

            sort(s+,s++m,cmp2);

            for (int j=,k;j<=m;j=k)

            {

                for (k=j;k<=m&&s[k].val==s[j].val;k++)

                {

                    num1[i][s[k].id]=j-;

                }

            }

        }

        for(int j=;j<=m;j++)

        {

            for(int i=;i<=n;i++) s[i].id=i, s[i].val=a[i][j];

            sort(s+,s++n,cmp1);

            for (int i=,k;i<=n;i=k)

            {

                for (k=i;k<=n&&s[k].val==s[i].val;k++)

                {

                    num2[s[k].id][j]=i-;

                }

            }

        }

        long long ans=;

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=m;j++)

            {

                long long A=b[num1[i][j]],B=b[num2[i][j]];

                long long p=A*B%mod;

                ans=(ans+p)%mod;

            }

        }

        printf("%lld\n",ans);

    }

    return ;

}