【DSY 4484】矩阵 题解（带限错排）

DSY 传送门。

（带限制）错排问题。

神仙题。

Solution

• 根据题目的问法，发现我们只想统计比给定矩阵 \(A\) 小的矩阵，记这个矩阵为 \(B\)。
  显然，\(B\) 的第 \(i\) 行一定从某个位置开始小于 \(A\) 的第 \(i\) 行，且前面的内容和 \(A\) 都是一样的。
  所以我们只需要枚举这个“开始变小”的位置然后统计每种情况的答案即可。
  这样枚举的复杂度是 \(O(n^2)\) 的，可以接受。
• 显然，第 \(i\) 行之后的行，可以随便排，只要满足是“好的矩阵”，它一定比 \(A\) 小。
  根据题目要求“竖直方向上相邻不同”，我们知道这题本质就是一个错排问题。
  也即是说，第 \(i+1\) 到 \(n\) 行随意排的总方案数就是 \(f_n^{n-i}\)，其中 \(f_n\) 为 \(n\) 个数的错排方案数。
  且显然，\(f_i=(f_{i-1}+f_{i-2})\times (i-1)\)，而这个式子我们已经在 GDOI2023 Day1 讲过。
• 再考虑第 \(i\) 行的方案如何统计。不妨假设我们在 \((i,j)\) 这个位置开始变小。
  需要注意的是此时第 \(i\) 行和第 \(i-1\) 行是不同的，而且我们还要保证竖直上相邻不同。
  所以这就是个带限制的错排问题——有些数可以放在任意位置，但有些数不能放在特定的某一位置上。
  因为 \([A_{i-1,j},A_{i-1,n}]\) 的数在 \([A_{i,j},A_{i,n}]\) 是不能出现在特定位置的。相反，\([A_{i-1,1},A_{i-1,j-1}]\) 的数在 \([A_{i,j},A_{i,n}]\) 可以放任意位置。
  所以我们倒序使用树状数组统计这些数然后倒序统计方案数。
  具体地，记 \(g_{i,j}\) 表示 \(i\) 个数排列，且有 \(j\) 个数有限制的排列方案数。
  经过简单推导，可得 \(g_{i,j}=g_{i,j-1}-g_{i-1,j-1}\)。
• 所以最终复杂度为 \(O(n^2\log n)\)。

Code

树状数组的统计见注释说明。代码量大概是 \(2k\)。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i) 
const int mod = 998244353, maxn = 2005, _ = 2000;
int n, a[maxn][maxn];
int fac[maxn], f[maxn], g[maxn][maxn];
int A[maxn][maxn];
int ans, tmp;

struct BIT{
	int t[maxn];
	BIT(){ memset(t, 0, sizeof t);}
	inline int lb(int x){ return x & (-x);}
	inline void add(int x, int k){
		for(int i = x; i <= n; i += lb(i)) (t[i] += k) %= mod;
	}
	inline int qry(int x){ int res = 0;
		for(int i = x; i; i -= lb(i)) (res += t[i]) %= mod;
		return res; 
	}
	inline bool ext(int x){//判断是否统计过数 x 
		return qry(x) - qry(x - 1) != 0 ? 1 : 0;
	} 
};

inline void init(){
	f[0] = fac[0] = 1;
	rep(i, 1, _) fac[i] = fac[i - 1] * i % mod;//预处理全排列方案数 
	rep(i, 2, _) f[i] = (f[i - 1] + f[i - 2]) % mod * (i - 1) % mod;
	rep(i, 0, _){ g[i][0] = f[i];
		rep(j, 1, i)
			g[i][j] = (g[i][j - 1] - g[i - 1][j - 1]) % mod;
	}
}
inline int pw(int x, int p){
	int res = 1;
	while(p){
		if(p & 1) res = res * x % mod;
		p /= 2, x = x * x % mod;
	} return res;
}

signed main(){
	scanf("%lld", &n), init();
	rep(i, 1, n) rep(j, 1, n) scanf("%lld", &a[i][j]);
	BIT t0;//值域树状数组 
	per(i, n, 1){//特殊处理第一行（没有上一行的限制） 
		(tmp += t0.qry(a[1][i]) * fac[n - i] % mod) %= mod;
		t0.add(a[1][i], 1);
	} 
	(ans += tmp * pw(f[n], n - 1) % mod) %= mod;
	rep(i, 2, n){
		BIT t1, t2, t3; tmp = 0;//值域树状数组 
		//t1：这一样出现过的数
		//t2：上一行出现过的数
		//t3：两行都出现过的数 
		per(j, n, 1){
			int cnt = t3.qry(n), flg = 0;//cnt：（倒序）这一行和上一行都出现过的数的个数 
			if(t2.ext(a[i][j])) cnt += 1;
			if(t1.ext(a[i - 1][j])) flg = 1, t1.add(a[i - 1][j], -1);//竖直方向上相邻的位置数不能相同 
			(tmp += t3.qry(a[i][j]) * g[n - j][cnt - 1] % mod) %= mod;//这个位置放一个两行都出现过的数 
			(tmp += (t1.qry(a[i][j]) - t3.qry(a[i][j])) * g[n - j][cnt] % mod) %= mod;
			//这个位置放一个目前只出现过一次的数（无限制） 
			if(flg) t1.add(a[i - 1][j], 1);
			
			//更新3个树状数组 
			t1.add(a[i][j], 1), t2.add(a[i - 1][j], 1);
			if(t2.ext(a[i][j])) t3.add(a[i][j], 1);
			if(t1.ext(a[i - 1][j])) t3.add(a[i - 1][j], 1);
		}
		(ans += tmp * pw(f[n], n - i) % mod) %= mod;
	} printf("%lld", (ans % mod + mod) % mod);
	return 0;
}

Thanks for reading.