【2022NOI模拟赛3T1】环 做题记录

对于一个长度为 $n$ 的 $01$ 串，下标从 $0$ 到 $n-1$。定义两种类型的操作:

$A$ 类型:选择一个 $x$，将序列循环右移 $x$ 位，也就是新序列的第 $(i+x)\mod\ n$ 位对应原序列的第 $i$ 位。例如：对于 $x=2$，$0110001100$ 将会变成 $1000110001$。

$B$ 类型:选择一个 $x$，满足序列的第 $x$ 个位置为 $1$，且第 $(x+1)\mod\ n$ 位置不为 $1$，交换序列的第 $x$ 个位置和第 $(x+1)\mod\ n$ 个位置的字符。

对于 $0101101011$，$x= 0$ 和 $x =3$ 均是不合法的，而 $x = 4$ 是合法的，操作后序列变为 $1101011010$。

给定 $n,k,l$。请构造一个由 $l$ 个长度为 $n$ 的 $01$ 串构成的序列 $s[]$，下标从 $0$ 开始。使得序列中每个串恰好有 $k$ 个 $1$。且对于所有满足 $0\le i<l$ 的 $i$，$s[i]$ 既可以通过一次 $A$ 类型的操作，也可以通过一次 $B$ 类型的操作，变为 $s[i+1]$。

举个例子，$001001$ 既可以通过一种 $A$ 类型的操作也可以通过一种 $B$ 类型的操作变为 $100100$：对于 $A$ 类型可以设 $x = 1$，对于 $B$ 类型可以设 $x = 2$。

$T$ 组数据。

$2\le n,l\le 100$，$0\le k\le n$，$1\le T\le 10$。

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

const int S=105;

int n,k,l;
int a[S],b[S];

inline int gcd(int x,int y)
{
	if(y==0) return 0;
	int t=x%y;
	while(t!=0) x=y,y=t,t=x%y;
	return y;
}

// 首先不难发现，只要求出 s[0] 即第一个字符串，
// 后面的就可以通过暴力枚举交换的位置哈希判断来得到，
// 那么考虑构造一个满足条件的 s[0]

void dfs(int n,int k) // 递归构造 n，k 时的 s[0]
{
	if(k==1)
	{
		a[1]=1;
		return;
	}
	// 若此时 n 和 k 互质，那么 n 一定不是 k 的倍数。考虑这 k 个 1 之间的 k 个间隔
	// 由于这 k 个间隔的总和一定是 n，所以
	// 显然有 k-n%k 个 floor(n/k) 和 n%k 个 ceil(n/k) 即 floor(n/k)+1。
	//
	// 考虑操作 B 的本质，其实就是让 a[i]--，a[i+1]++，
	// 而这样也会让位置 i 上原本的 1 距离上一个 1 的距离增加 1，
	// 而位置 i 之后最近的那个 1 距离它之前的 1 的距离会减去 1。
	//
	// 也就是说，若设 b[i] 为第 i 个 1 距离第 i-1 个 1 的距离，也就是它们的位置之差，
	// 特别的，b[1] 表示第 1 个 1 距离第 k 个 1 的距离，那么操作 B 相当于让 b[i]++，b[i+1]--。
	//
	// 那么把等于 floor(n/k) 的 b[i] 都看成 1，把等于 floor(n/k)+1 的 b[i] 看成 0，
	// 递归处理 n=k，k=k-n%k 的情况即可。
	
	// 若 n 和 k 不互质，那么 ceil(n/k) 显然是不可能恰好等于 floor(n/k)+1 的，此时便无解，
	// 因为 b[i] 怎么加减都会出现新的未出现过的数值，不可能和原来的 b 循环同构。
	dfs(k,k-n%k);
	int val0=n/k+1,val1=n/k;
	for(int i=1;i<=k;i++) b[i]=a[i]==0?val0:val1;
	for(int i=1;i<=n;i++) a[i]=0;
	int pos=n; // 钦定最后一位为 1，因为 s[0] 是循环同构的
	for(int i=k;i>=1;i--) a[pos]=1,pos=(pos-b[i]-1+n)%n+1;
}

set<__int128_t> st; // 把 01 序列当作二进制数进行哈希

inline __int128_t calc(int a[]) // 计算哈希
{
	__int128_t pw2=1,has=0;
	for(int i=1;i<=n;i++)
	{
		has+=a[i]*pw2;
		pw2*=2;
	}
	return has;
}

inline void slove()
{
	scanf("%d%d%d",&n,&k,&l);
	if(gcd(n,k)!=1) // 无解情况：n 和 k 不互质
	{
		puts("NO");
		return;
	}
	st.clear();
	puts("YES");
	for(int i=1;i<=n;i++) a[i]=0;
	dfs(n,k);
	st.insert(calc(a));
	for(int i=1;i<=n;i++) // 预处理好和 s[0] 循环同构的字符串
	{
		for(int j=1;j<=n;j++) b[(j+i-1)%n+1]=a[j];
		st.insert(calc(b));
	}
	for(int i=1;i<=l;i++)
	{
		for(int j=1;j<=n;j++) printf("%d",a[j]);
		printf("\n");
		for(int j=1;j<=n;j++) // 暴力找下一个
		{
			for(int k=1;k<=n;k++) b[k]=a[k];
			if(b[j]==1&&b[j%n+1]==0)
			{
				b[j]=0;
				b[j%n+1]=1;
				if(st.count(calc(b)))
				{
					for(int k=1;k<=n;k++) a[k]=b[k];
					break;
				}
			}
		}
	}
}

int main()
{
	int T=1;
	scanf("%d",&T);
	while(T-->0)
	{
		slove();
	}
	return 0;
}