[Cnoi2020] 高维
题目背景
> 本质上，幻想乡是高维的。
题目描述
Cirno 捕获了一只 $n$ 维蚂蚁，它想从 $S(0,0,...,0)$ 爬到 $T(1,1,...,1)$ 。
被封闭在这个 $1\times1\times...\times1$ 的方格中，蚂蚁每一步只能爬向一个坐标相邻的点。
现在 Cirno 想考考你蚂蚁最多能找到多少条从 $S$ 到 $T$ 的路径两两没有交点( 除 $S$, $T$ )。
并要求你构造这样一组路径。
输入输出格式
输入格式
一行，一个整数 $n$ 。
输出格式
第一行，一个整数 $t$，表示最多的路径数。
以下 $t$ 行，每行一条合法路径。
合法路径表示方式 :
> $S$ [空格] $P_1$ [空格] $P_2$ [空格] ... [空格] $T$
其中 $P_i$ 是一个二进制压缩的 $01$ 串 表示一个 $n$ 维坐标。
**请不要输出多余的空格**。
输入输出样例
输入样例 #1
2输出样例 #1
2
0 1 3
0 2 3说明
**「本题使用 Special Judge」**
### Sample1解释
第 $1$ 条路径：$(0,0) \rightarrow (0,1) \rightarrow (1,1)$
第 $2$ 条路径：$(0,0) \rightarrow (1,0) \rightarrow (1,1)$
二者除了 $S$ 与 $T$ 无交点。
### 数据范围约定
**「本题不采用捆绑测试，数据有梯度」**
对于 100% 的数据 $3 \le n \le 60$。
### 后置代码片段
- 二进制压位函数
```cpp
/**
* For only cpp11, cpp14, cpp17, cpp20.
*
* @param: __s : The binary high-dimension position inputed.
* @return: Standard output format( U64 ).
**/
unsigned long long zip( std::string __s )
{ unsigned long long __r = 0;
for( auto __c : __s )
{ ( __r <<= 1ull ) |= ( __c - 0x30 ); }
return __r; }
```
- SPJ代码
```cpp
//SPJ
#include "testlib.h"
#include<bits/stdc++.h>
typedef unsigned long long ULL;
typedef std::vector<std::string> SEQ;
typedef std::string STR;
SEQ split( std::string _par, char _sgn )
{ SEQ _rat = SEQ();
STR _rem = STR();
for( char __c : _par )
{ if( __c = _sgn ) _rat.push_back( _rem ), _rem = "";
else _rem += __c; }
if( _rem != "" ) _rat.push_back( _rem );
return _rat; }
ULL to_ULL( std::string _str )
{ ULL _rat = 0;
for( char __c : _str )
{ ( _rat *= 10ull ) += (ULL)( __c - '0' ); }
return _rat; }
bool isPw2( ULL x )
{ return !( x & (x - 1ull) ); }
std::map<ULL, bool> MP;
int main(int argc, char* argv[]) {
registerTestlibCmd(argc, argv);
ULL n = inf.readLong();
ULL S = 0, T = (1ull << n) - 1ull;
ULL N = ouf.readLong();
if( N != n ) quitf( _wa, "Count paths wrongly." );
ouf.readEoln();
while( n -- ) {
std::string path = ouf.readLine();
ULL _lst = 0;
for( auto N : split( path, " " ) )
{ ULL _now = to_ULL( N );
if( _now != S and _now != T and MP[_now] )
{ quitf( _wa, "Paths crossing" ); }
if( !isPw2( _now ^ _lst ) )
{ quitf( _wa, "Wrong path format" ); }
_lst = _now; MP[_now] = true; }
if( _lst != T ) quitf( _wa, "Wrong path ending" );
}
quitf( _ok, "Accepted" );
return 0;
}
```