首先枚举哪一位分出大小， 然后计算比它小的方案数有多少种。
方案数 = 当前行的方案数 * 下面所有行的方案数。 如果下面还有x行，
那么下面所有行的方案数为 g ^ x， g 为全错排的方案数， 当前行的要预处理出f[ i ][ j ]
f[ i ][ j ] 表示有 i 个空没填， 有 j 个是有限制的方案数， 然后讨论一下就好啦。
#include<bits/stdc++.h> #define LL long long #define LD long double #define ull unsigned long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ALL(x) (x).begin(), (x).end() #define fio ios::sync_with_stdio(false); cin.tie(0); using namespace std; const int N = 2000 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; const double eps = 1e-8; const double PI = acos(-1); template<class T, class S> inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;} template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;} template<class T, class S> inline bool chkmax(T& a, S b) {return a < b ? a = b, true : false;} template<class T, class S> inline bool chkmin(T& a, S b) {return a > b ? a = b, true : false;} int n; int f[N][N], a[N][N]; int pos[N]; bool in[N]; struct Bit { int a[N]; void init() { memset(a, 0, sizeof(a)); } void modify(int x, int v) { for(int i = x; i < N; i += i & -i) a[i] += v; } int sum(int x) { int ans = 0; for(int i = x; i; i -= i & -i) ans += a[i]; return ans; } int query(int L, int R) { if(L > R) return 0; return sum(R) - sum(L - 1); } } bit, bit2; int F[N], Finv[N], inv[N]; void init() { F[0] = Finv[0] = inv[1] = 1; for(int i = 2; i < N; i++) inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod; for(int i = 1; i < N; i++) F[i] = 1LL * F[i - 1] * i % mod; for(int i = 1; i < N; i++) Finv[i] = 1LL * Finv[i - 1] * inv[i] % mod; for(int i = 0; i < N; i++) { f[i][0] = F[i]; for(int j = 1; j <= i; j++) { f[i][j] = (f[i][j - 1] - f[i - 1][j - 1] + mod) % mod; } } } int C(int n, int m) { if(n < 0 || n < m) return 0; return 1LL * F[n] * Finv[m] % mod * Finv[n - m] % mod; } int power(int a, int b) { int ans = 1; while(b) { if(b & 1) ans = 1LL * ans * a % mod; a = 1LL * a * a % mod; b >>= 1; } return ans; } int main() { init(); scanf("%d", &n); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf("%d", &a[i][j]); int ans = 0; for(int i = 1; i <= n; i++) { bit.init(); bit2.init(); memset(in, 0, sizeof(in)); if(i == 1) { for(int j = 1; j < n; j++) { int cnt = a[i][j] - 1 - bit.query(1, a[i][j] - 1); int way = 1LL * cnt * F[n - j] % mod * power(f[n][n], n - 1) % mod; add(ans, way); bit.modify(a[i][j], 1); } } else { for(int j = 1; j < n; j++) { int c1 = bit.query(1, a[i][j] - 1); int c2 = a[i][j] - 1 - bit2.query(1, a[i][j]) - c1; int allc1 = bit.query(1, n); int allc2 = n - j + 1 - allc1; if(a[i - 1][j] > a[i][j]) { if(in[a[i - 1][j]]) { if(c1) add(ans, 1LL * c1 * f[n - j][allc2] % mod * power(f[n][n], n - i) % mod); if(c2) add(ans, 1LL * c2 * f[n - j][allc2 - 1] % mod * power(f[n][n], n - i) % mod); } else { if(c1) add(ans, 1LL * c1 * f[n - j][allc2 - 1] % mod * power(f[n][n], n - i) % mod); if(c2) add(ans, 1LL * c2 * f[n - j][allc2 - 2] % mod * power(f[n][n], n - i) % mod); } } else { if(in[a[i - 1][j]]) { if(c1) add(ans, 1LL * c1 * f[n - j][allc2] % mod * power(f[n][n], n - i) % mod); if(c2) add(ans, 1LL * c2 * f[n - j][allc2 - 1] % mod * power(f[n][n], n - i) % mod); } else { if(c1) add(ans, 1LL * c1 * f[n - j][allc2 - 1] % mod * power(f[n][n], n - i) % mod); if(c2 > 1) add(ans, 1LL * (c2 - 1) * f[n - j][allc2 - 2] % mod * power(f[n][n], n - i) % mod); } } if(!in[a[i - 1][j]]) { bit.modify(a[i - 1][j], 1); } if(bit.query(a[i][j], a[i][j])) bit.modify(a[i][j], -1); bit2.modify(a[i][j], 1); in[a[i][j]] = true; } } } printf("%d ", ans); return 0; } /* */