自动搬运

查看原文

来自洛谷，原作者为

	Rubidium_Chloride No, I can't.

搬运于2025-08-24 22:18:03，当前版本为作者最后更新于2020-03-02 11:53:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

谔谔谔这题是数学+构造题。

进博客看效果更好呦！

进入正题：

1.题目大义

有一个长为$n$的$01$串，初始值为$0$，每次可以将它的一位取反，最终值为$2^{n}-1$，让你求出这样不相交的的$01$串的个数的最大值。

2.分析

看到样例和SPJ第一问应该就出来了吧……

对于$3$维的情况，很容易构造出一种$3$条的情况如下：

$0$-$1$-$3$-$7$

$0$-$2$-$6$-$7$

$0$-$4$-$5$-$7$

对于这种情况，本蒟蒻就猜想，是不是对于每一个$n$,答案的第一问都是$n$呢？

3.证明

3.1 先证对于每一个$n$，$n$维空间中最多$n$条不相交路径

$\because$ 在$n$维空间中，每个点连出$n$条边；（考虑其每一个二进制位取反所得的结果即可得到。）

$\therefore$ 0号节点也不例外；

$\because$ 路劲都不能相交；

$\therefore$ 最多有$n$条路径，命题成立。

3.2 再给出一组构造

对于每一个$n$位$01$串，从右开始其每一位分别设为$a_{0}\ a_{1}$……$a_{n-1}$.

于是我们可以轻松地给出这样$n$条路径的一组构造（以下均写改变的$a_{i}$的下标）：

$0$ -- $1$ …… -- $n-1$

$1$ -- $2$ …… -- $n-1$ -- $0$

……

$n-1$ -- $0$ …… -- $n-2$

4.CODE

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k[69]={1},n;//n<=60，所以要开long long 
inline int read(){//快读提高速度 
    register int x=0;char ch=getchar();
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x;
}
int main(){
	n=read();
	printf("%lld",n);//由3.证明，直接输出n即可 
	for(register int i=1;i<=n-1;i++) k[i]=k[i-1]<<1;//预计算2的幂次，为下面压缩2进制数做准备 
	for(register int i=0;i<=n-1;i++){
		printf("\n0");//有特殊的输入要求就按题目说的来，行末无空格 
		for(register ll j=0,m=0;j<=n-1;j++){
			m+=k[(i+j)%n];printf(" %lld",m);//同Line15，千万不能忘了mod n，否则RE 
		}
	}
	return 0;
}//皆大欢喜

~END~（祝大家看得开心，有意见可以提出来