[思维构造] 题解 Omkar and Duck

题目链接

题目大意

构造一个 \(n\times n\) 的矩阵，每个元素取值范围为 \([0,10^{16}]\) ，使得所有从 \((1,1)\) 仅往下或往右走走到 \((n,n)\) 的路径的权值两两不同（一条路径的权值定义为这条路径经过的所有元素之和）。

\(1\le n\le 25\) 。

题目分析

思路一

神 @Imakf 提供了一种构造方法，把向右走认为是字符“a”，向左走认为是字符“b”，把所有 \((1,1)\) 到 \((n,n)\) 的路径写成字符串然后按照字典序排序后依次钦定权值为 \(0,1,\dots,{2(n-1)\choose n-1}-1\) ，然后按照这个钦定的权值去给每个格子赋值就行了。

这样做为什么是对的？如果将所有路径插入 Trie 树，那么某个点 \((x,y)\) 到 \((n,n)\) 的所有路径在 Trie 树上面是连续的，按照上面的构造方法所有路径的权值也就是连续的一段，由此不难发现这样构造就是正确的（或者说钦定的权值并不会出现冲突）。

具体如何实现？认为左上角是 \((1,1)\) 右下角是 \((n,n)\) ，给每个格子 \((x,y)\) 记录一个 \([L,R]\) 表示 \((x,y)\) 到 \((n,n)\) 的所有路径的权值取值范围，先钦定第 \(n\) 列的所有元素取值 \(0\) ，然后按列数从大到小，行数从大到小确定每个格子元素的取值，先认为当前格子取值为 \(0\) ，看从当前格子向下走和向右走的权值是否有重复，如果有的话就加大当前格子下面格子的取值。这样构造在极限数据 \(n=25\) 时每个元素取值是符合范围的。

思路二

考虑二进制拆分，使用如下构造方式：

 0  0  0  0
 1  2  4  8
 0  0  0  0
 4  8 16 32

（奇数行所有元素为 \(0\) ，偶数行位置 \((x,y)\) 的值为 \(2^{x+y-3}\) ）

这种方法相当于把某个数二进制表示下若干连续的 \(1\) 绑定在一起，连续的 \(1\) 在同一行一起经过，不连续的 \(1\) 在不同行经过，不难发现这样构造也不会出现重复。

参考代码

思路一的代码：

#include
#include
#include
#include
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
templatevoid read(T&x){
	static char c;static int f;
	for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
templatevoid write(T x){
	static char q[65];int cnt=0;
	if(x<0)pc('-'),x=-x;
	q[++cnt]=x%10,x/=10;
	while(x)
		q[++cnt]=x%10,x/=10;
	while(cnt)pc(q[cnt--]+'0');
}
long long L[35][35],R[35][35],val[35][35];
int main(){
	int n;read(n);
	for(int i=1;i<=n;++i){
		val[i][n]=0;
		L[i][n]=R[i][n]=0;
	}
	for(int j=n-1;j>=1;--j){
		val[n][j]=0;
		L[n][j]=R[n][j]=L[n][j+1];
		for(int i=n-1;i>=1;--i){
			val[i][j]=0;
			if(L[i+1][j]<=R[i][j+1]){
				long long delta=R[i][j+1]-L[i+1][j]+1;
				L[i+1][j]+=delta,R[i+1][j]+=delta;
				val[i+1][j]+=delta;
			}
			L[i][j]=L[i][j+1];R[i][j]=R[i+1][j];
		}
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;pc(" \n"[j==n]),++j)
			write(val[i][j]);
	fflush(stdout);
	int q;read(q);
	while(q--){
		long long x;read(x);
		int nx=1,ny=1;
		while(nx<=n&&ny<=n){
			write(nx),pc(' '),write(ny),pc('\n');
			if(nx