解题思路
??考虑单独计算每个数的贡献，假设\([1,n]\)中的某个数对答案有贡献，则这一行其他的数都要比它大，所以这一行其他数一共有\(C(n^2-i, n-1)\)种选法，而这一行的方案数就是\(n! \times C(n^2-i, n-1)\)，对于其他的数来说，不管它们是否小于\(n\)，随意放置都不会影响这一行对答案的贡献，所以其他的数共有\((n^2-n)!\)种放置方案，一共有\(n\)行，所以我们枚举的数可以放\(n\)行中，答案再乘上\(n\)就是我们枚举的当前数字\(i\)的方案数。
??所以最终答案就是\(\sum_{i=1}^n n \times C(n^2-i, n-1) \times n! \times (n^2-n)!\)
代码
const int maxn = 5e3+10;
const int maxm = 5e3*5e3+10;
int fac[maxm], inv[maxm];
ll fp(ll x, ll y) {
ll ans = 1;
while(y) {
if(y&1) ans = ans*x%MOD;
x = x*x%MOD;
y >>= 1;
}
return ans;
}
void init() {
fac[0] = 1;
for(int i = 1; i<maxm; ++i) fac[i] = 1LL*fac[i-1]*i%MOD;
inv[maxm-1] = fp(fac[maxm-1], MOD-2);
for(int i = maxm-2; i>=0; --i) inv[i] = 1LL*inv[i+1]*(i+1)%MOD;
}
int main() {
IOS;
init();
int __; cin >> __;
while(__--) {
ll n; cin >> n;
ll ans = 0;
for (int i = 1; i<=n; ++i) {
ll t = n*fac[n*n-i]%MOD*inv[n-1]%MOD*inv[n*n-i-n+1]%MOD;
t = t*fac[n]%MOD*fac[n*n-n]%MOD;
ans = (ans+t)%MOD;
}
cout << ans << endl;
}
return 0;
}