自动搬运

查看原文

来自洛谷，原作者为

	expin **

搬运于2025-08-24 21:25:46，当前版本为作者最后更新于2018-08-05 17:08:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

去年，搞竞赛的同学给我看了这题，觉得挺有意思的，但是根本不知道分治是啥，所以作罢。不久前在写组合数问题P2822时，尽管我用了题解里的递推公式，但还是WA。于是我想把杨辉三角对2取模输出看下结果，这是12行内的结果：

            1
           1 1 
          1 0 1 
         1 1 1 1 
        1 0 0 0 1 
       1 1 0 0 1 1 
      1 0 1 0 1 0 1 
     1 1 1 1 1 1 1 1 
    1 0 0 0 0 0 0 0 1 
   1 1 0 0 0 0 0 0 1 1 
  1 0 1 0 0 0 0 0 1 0 1
 1 1 1 1 0 0 0 0 1 1 1 1

发现0的分布很有规律，突发奇想能否用这个规律来解这题。

优化了一下递推公式

a[i][j]=a[i-1][j]^a[i-1][j-1];

异或和(a+b)%2有相同的效果，后来发现甚至可以直接用一维数组实现，那就不客气了（滑稽）。

思路如下：行数是2的n次方，以这个数组为基础，奇数行遇1输出"/",偶数行遇连续两个1输出"/__"，遇0补上相应的空格即可。

以下是代码：

#include<iostream>
using namespace std;
int n,a[1030]={1};
int main(){
	cin>>n;
    for(int i=0;i<1<<n;++i){
        for(int j=1;j<(1<<n)-i;++j)cout<<" ";//前导空格
		for(int j=i;j>=0;--j)a[j]^=a[j-1];//修改数组
		if(!(i%2))for(int j=0;j<=i;++j)cout<<(a[j]?"/\\":"  ");//奇数行
		else for(int j=0;j<=i;j+=2)cout<<(a[j]?"/__\\":"    ");//偶数行
		cout<<endl;
    }
    return 0;
}