题解 P1498 【南蛮图腾】

· · 题解

去年，搞竞赛的同学给我看了这题，觉得挺有意思的，但是根本不知道分治是啥，所以作罢。不久前在写组合数问题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;
}