CF1392E Omkar and Duck 做题记录

构造一个 $n\times n$ 的矩阵，满足元素 $\le 10^{16}$。

$q$ 次询问，每次给出一条 $(1,1)\to (n,n)$ 只能向下向右走的路径上的元素的和，你需要保证矩阵对于这 $q$ 次询问路径都能唯一确定。

$1\le n\le 25$，$1\le q\le 10^3$。

观察到我们只要知道偶数行在哪里，就可以得知整条路径，所以不妨考虑构造一个奇数行均为 $0$，偶数行均不为 $0$ 的矩阵。

考虑偶数行的取值，显然可以考虑二进制拆位，给每一个处于偶数行的位置都分配一个 $2^p$ 的权值。

考虑 $p$ 的取值，由于不能向左走，所以不同行的 $p$ 可以有重复的。第一行显然必须是 $\{1,2,3,4,5,\dots\}$，第二行则可以是 $\{3,4,5,6,7,\dots\}$ 因为不能向左走。所以第 $2i$ 行开头的 $p$ 最小可以取第 $2_{i-1}$ 行从左往右数第 $3$ 个 $p$。

这样我们一共用了 $n+2(\lfloor\frac{n}{2}\rfloor-1)$ 个 $p$，$n=25$ 时用了 $25+2\times 11=47$ 个 $p$，$2^{47}\le 10^{16}$，构造满足限制。

不难发现这样构造之后若路径的权值和为 $sum$，则 $sum$ 的二进制序列（低位在前高位在后）$S$ 中连续的 $1$ 对应在同一偶数行中走，特判 $n$ 的奇偶性输出方案即可。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=30,BS=500;

int n,q;
long long a[S][S];

int main()
{
	scanf("%d",&n);
	int cnt=0;
	for(int i=2;i<=n;i+=2)
	{
		long long mul=1<<i-2;
		for(int j=1;j<=n;j++) a[i][j]=mul,mul<<=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) printf("%lld ",a[i][j]);
		printf("\n");
		fflush(stdout);
	}
	scanf("%d",&q);
	while(q--)
	{
		long long sm;
		scanf("%lld",&sm);
		int lim=n+(n/2-1)*2-!(n&1);
		int x=1,y=1;
		for(int i=-1;i<=lim;i++)
		{
			printf("%d %d\n",x,y);
			fflush(stdout);
			if((i>=0&&(sm>>i&1))&&!(sm>>i+1&1)) x++;
			else if((1<0||!(sm>>i&1))&&(sm>>i+1&1)) x++;
			else y++;
		}
	}
	return 0;
}