题目大意
将 \(1\sim n^2\) 填入 \(n\times n\) 的网格 \(A\) 中，对于每个格子满足以下条件之一：
-
该列中存在大于它的数。
-
该行中存在小于它的数。
求方案数。
思路分析
首先有一个比较显然的结论：对于一个不合法的方案，有且仅有一个数不满足任何一个条件。
考虑反证法，假设有两个数都不满足任何一个条件，设这两个数分别位于 \((x_1,y_1),(x_2,y_2)\)，则有：\(A_{x_1,y_1}>A_{x_1,y_2}>A_{x_2,y_2}\)，\(A_{x_2,y_2}>A_{x_2,y_1}>A_{x_1,y_1}\)，存在矛盾，而多个数的情况可以归纳为两个数的情况，故结论成立。
正难则反，考虑计算不合法的方案数：
设不满足任何条件的数为 \(i\)，考虑到 \(i\) 是所在列中最大的数，且是所在行中最小的数，故所在行的填法为 \(A_{n^2-i}^{n-1}\)，所在列的填法为 \(A_{i-1}^{n-1}\)，其他的地方随便填，一定满足条件，填法为 \((n-1)^2!\)，再考虑 \(i\) 的位置，故得出不合法的方案数的计算式为：
\[n^2\times (n-1)^2!\times\sum_{i=n}^{n^2-n+1}A_{n^2-i}^{n-1}A_{i-1}^{n-1}
\]
那么合法的方案数只需要用 \(n^2!\) 减一下就可以了。
如果预处理阶乘和阶乘逆元，那么计算的时间复杂度为 \(O(n^2)\)。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=250100,V=250000,mod=998244353;
#define int long long
int fac[N],inv[N];
int n,ans;
int q_pow(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int A(int n,int m){
if(n<m) return 0;
return fac[n]*inv[n-m]%mod;
}
signed main(){
scanf("%lld",&n);
int n2=n*n;
fac[0]=1;
for(int i=1;i<=n2;i++) fac[i]=fac[i-1]*i%mod;
inv[n2]=q_pow(fac[n2],mod-2);
for(int i=n2;i>=1;i--) inv[i-1]=inv[i]*i%mod;
for(int i=n;i<=n2-n+1;i++)
ans=(ans+A(n2-i,n-1)*A(i-1,n-1)%mod)%mod;
ans=(ans*fac[(n-1)*(n-1)]%mod)*n2%mod;
ans=(fac[n*n]-ans+mod)%mod;
cout<<ans<<'\n';
return 0;
}