CF1392E Omkar and Duck 做题记录

构造一个 n×nn\times n 的矩阵,满足元素 1016\le 10^{16}

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

1n251\le n\le 251q1031\le q\le 10^3

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

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

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

这样我们一共用了 n+2(n21)n+2(\lfloor\frac{n}{2}\rfloor-1)ppn=25n=25 时用了 25+2×11=4725+2\times 11=47pp24710162^{47}\le 10^{16},构造满足限制。

不难发现这样构造之后若路径的权值和为 sumsum,则 sumsum 的二进制序列(低位在前高位在后)SS 中连续的 11 对应在同一偶数行中走,特判 nn 的奇偶性输出方案即可。

代码如下:

#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;
}