题面
现有一个 n\times n 的网格，定义一个合法的点为满足该点是不是该列的最大值或该点不是该行的最小值，求每个点都合法的网格的数量，答案对 998244353 取模。
例如 n=2 时的情况，满足条件的有 8 组，其中的一组如下：
13
42
观察到 1 不是所在列的最大值， 2 不是所在列的最大值， 3 不是所在行的最小值， 4 不是所在行的最小值。
解题思路
对于每个不满足条件的网格，有且仅有一个点不满足条件。
证明如下：
反证法，假如有 >1 个点不满足条件，令其中两个点的坐标分别为 i1,j1 和 i2,j2 ，根据题意，显然有 a_{i1,j1}>a_{i2,j1}>a_{i2,j2} ，也就是 a_{i1,j1}>a_{i2,j2} ，也显然有 a_{i1,j1}<a_{i1,j2}<a_{i2,j2} ，也就是 a_{i1,j1}<a_{i2,j2} ，矛盾。
所以我们仅需枚举每个点，计算当该点不满足条件时的方案数，再用所有排列数减去它即可。
假设第 i 个点不满足条件，注意到大于 i 的数共有 n^2-i 个，所以共有 n^2-i 个数可以填入行内，小于 i 的数共有 i-1 个，所以共有 i-1 个数可以填入列内。
每行每列都有 n-1 个空位可填，所以对于 i 不满足条件的情况，该行该列共有 A_{n^2-i}^{n-1}A_{i-1}^{n-1} 中组合。
求出了对于每个 i 的组合方案数，只需将其加在一起即可。除去每行每列，剩余有 (i-1)^2! 个空位，直接乘上即可。 i 有 n^2 中选择方案，将其乘上答案可得最终结果。
另外当 i<n 或 i\ge n^2-n+1 时式子不合法，所以仅需枚举 n 至 n^2-n+1 即可。
最终的式子为 (n-1)^2!\times n^2\times \sum\limits_{i=n}^{n^2-n+1}A_{n^2-i}^{n-1}A_{i-1}^{n-1} 。
代码实现
注意线性预处理逆元。
若不预处理，则时间复杂度为 O(n^4) ，无法通过本题。
核心代码如下：
for(int i=n;i<=n*n-n+1;i++) ans=(ans+A(n*n-i,n-1)%mod*A(i-1,n-1)%mod)%mod;
ans=(fac[n*n]-n*n*fac[(n-1)*(n-1)]%mod*ans%mod+mod)%mod;
如有问题欢迎指出。