出题人题解 | #筱玛的网格#

原题解链接：https://ac.nowcoder.com/discuss/151505

首先，不难发现对角线上的元素一定一样。

那么我们就可以把$n\times mn\; \backslash times\; m$的网格看成一个$n+m-1n\; +\; m-\; 1$长度的序列。

对于第二个$valval$价值的限制，从小到大填数就行了。

先填‘（’，$DPDP$出填了以后有多少答案;如果$>K>\; K$则继续，否则$KK$减去这个方案数，然后填上右括号。

#include<bits/stdc++.h>
#define pi pair<int,int>
#define mk make_pair
#define N 505
#define int long long
using namespace std;bool vis[N*N];
pi id[N*N];int n,m,K,a[N][N],ans[N*N],dp[N][N];double ddp[N][N];
inline void solve(int x,int y){
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;ans[x+y-1]=1;
	memset(ddp,0,sizeof(ddp));ddp[0][0]=1;
	for (int i=1;i<=n+m-1;i++){
		if (!ans[i]){
			for (int j=0;j<=i;j++)
				ddp[i][j+1]=ddp[i][j+1]+ddp[i-1][j];
			for (int j=1;j<=i;j++)
				ddp[i][j-1]=(ddp[i][j-1]+ddp[i-1][j]);
		}
		else if (ans[i]==1){
			for (int j=0;j<=i;j++)
				ddp[i][j+1]=ddp[i-1][j]+ddp[i][j+1];
		}
		else if (ans[i]==2){
			for (int j=1;j<=i;j++)
				ddp[i][j-1]=(ddp[i][j-1]+ddp[i-1][j]);
		}
	}
	if (ddp[n+m-1][0]>=K) return;
	for (int i=1;i<=n+m-1;i++){
		if (!ans[i]){
			for (int j=0;j<=i;j++)
				dp[i][j+1]=dp[i][j+1]+dp[i-1][j];
			for (int j=1;j<=i;j++)
				dp[i][j-1]=(dp[i][j-1]+dp[i-1][j]);
		}
		else if (ans[i]==1){
			for (int j=0;j<=i;j++)
				dp[i][j+1]=dp[i-1][j]+dp[i][j+1];
		}
		else if (ans[i]==2){
			for (int j=1;j<=i;j++)
				dp[i][j-1]=(dp[i][j-1]+dp[i-1][j]);
		}
	}
	if (dp[n+m-1][0]<K){
		K-=dp[n+m-1][0];
		ans[x+y-1]=2;
	}
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&K);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++) scanf("%lld",&a[i][j]),id[a[i][j]]=mk(i,j);
	solve(1,1);
	for (int i=1;i<=n*m;i++){
		int x=id[i].first;int y=id[i].second;
		if (vis[x+y]) continue;
		solve(x,y);
		vis[x+y]=1;
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			int tmp=i+j-1;
			if (ans[tmp]==1) putchar('(');
			else if (ans[tmp]==2) putchar(')'); 
		}
		putchar('\n');
	}
	return 0;
}