题解 P6161 【[Cnoi2020]高维】

· · 题解

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

进博客看效果更好呦！

进入正题：

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条不相交路径

$\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~（祝大家看得开心，有意见可以提出来