题目概述

有 $n\times m$ 的网格，现在要不重复的填入 $1\sim nm$ ，如果一个格子比同行同列的数都大就称这个格子占领了这行这列。求只有一个格子占领一行一列时的方案数。

解题报告

显然 $nm$ 绝对占领一行一列，所以只需要考虑其他格子不占领一行一列就行了。

考虑从大到小放，那么除了 $nm$ 之外其他数都必须放在之前覆盖过的行和列中。

我们发现每个数放下去之后有三种情况：1.处在之前覆盖的列上，占领一行。2.处在之前覆盖的行上，占领一列。3.处在之前的交点，没有占领。

所以定义 $f_{i,j,k}$ 表示已经占领了 $i$ 行 $j$ 列，还剩下 $k$ 个交点的方案数。$f_{1,1,0}=nm$ ，根据三种情况转移一下，然后 $f_{n,m,0}$ 就是答案。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=80,maxk=maxn*maxn;

int n,m,te,MOD,f[maxn+5][maxn+5][maxk+5];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d%d%d",&n,&m,&MOD);
        for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) for (int k=0;k<=n*m;k++) f[i][j][k]=0;f[1][1][0]=n*m;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                for (int k=i*j;~k;k--)
                    if (f[i][j][k]){
                        if (i<n) AMOD(f[i+1][j][k+j-1],(LL)f[i][j][k]*(n*j-i*j)%MOD);
                        if (j<m) AMOD(f[i][j+1][k+i-1],(LL)f[i][j][k]*(m*i-i*j)%MOD);
                        if (k) AMOD(f[i][j][k-1],(LL)f[i][j][k]*k%MOD);
                    }
        printf("%d\n",f[n][m][0]);
    }
    return 0;
}