由 洛谷 P5461 P1498 引发的杨辉三角形特性思考

 

源自洛谷 P5461 https://www.luogu.com.cn/problem/P5461

 

题目描述

现有 2n * 2n (n <= 10) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵,每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免,剩下 3 个小矩阵中,每一个矩阵继续分为 4 个更小的矩阵,然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。

给出 n,请输出每名作弊者的命运,其中 0 代表被赦免,1 代表不被赦免。

输入格式

一个整数 n。

输出格式

 2n * 2n 的 01 矩阵,代表每个人是否被赦免。数字之间有一个空格。

输入 

   3 

输出

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

这道题引发了我的一些思考,这道题固然可以递归做,不停的递归四个小正方形矩阵,并将左上角清零,直到无法再划分小正方形矩阵为之。

但是我们观察这个矩阵,我们可以惊讶的发现,这个矩阵的右半部分,正是杨辉三角的值%2的结果,于是我们可以有代码:
#include<iostream>
#include<cmath>
using namespace std;
int a[1050][1050];
int main()
{
    int n;
    cin >> n;
    n = 1 << n;
    a[0][n+1] = 1;
    for (int i = 1;i <= n;i ++)
    {
        for (int j = 1;j <= n;j ++)
        {
            a[i][j] = a[i-1][j]%2 + a[i-1][j+1]%2;
            cout << (a[i][j]%2) << ' ';
        }
        cout << endl;
    }
    
    return 0;
}

 

值得注意的是:

1. 1 << n 的含义为把1按二进制左移n位,即2的n次方

2. 当n较大时,会爆int,所以我们在状态转移的时候就把结果%2,最后输出答案的时候也%2,这样就不会爆int

3. 当然也可以把  a[i][j] = a[i-1][j]%2 + a[i-1][j+1]%2;  换成  a[i][j] = a[i-1][j] ^ a[i-1][j+1];  这样输出答案的时候就不用%2

4. ^ 为异或运算符,0 ^ 0 = 1, 1 ^ 1 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1

 

同样的有洛谷 P1498 南蛮图腾 ,此题也可以用杨辉三角形的 %2 特性做

https://www.luogu.com.cn/problem/P1498

 

题目描述

自从到了南蛮之地,孔明不仅把孟获收拾的服服帖帖,而且还发现了不少少数民族的智慧,他发现少数民族的图腾往往有着一种分形的效果,在得到了酋长的传授后,孔明掌握了不少绘图技术,但唯独不会画他们的图腾,于是他找上了你的爷爷的爷爷的爷爷的爷爷……帮忙,作为一个好孙子的孙子的孙子的孙子……你能做到吗?

输入格式

每个数据一个数字,表示图腾的大小(此大小非彼大小) n<=10

输出格式

这个大小的图腾

输入#1

2

输出#1

   /\
  /__\
 /\  /\
/__\/__\

输入#2

3

输出#2

       /\
      /__\
     /\  /\
    /__\/__\
   /\      /\
  /__\    /__\
 /\  /\  /\  /\
/__\/__\/__\/__\


可以看出图腾有2的n次方行,而且带有一定的规律:

1. 当行数为奇数时,若对应数字为1,则输出 /\

2. 当行数为偶数时,若对应数字为1,则输出 /__\    并跳过下个数字继续循环

3. 当对应数字为0时,输出“  ”(即两个空格)

4. 每行的前导空格数量为 2n - i (i为行数)

 

对应的杨辉三角形%2如下图:

            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


则代码有:

#include<iostream>
using namespace std;
int f[1050][1050];
int main()
{
    int n;
    cin >> n;
    n = 1 << n;
    int t = n;
    f[0][n+1] = 1;
    for (int i = 1;i <= n;i ++)
    {
        for (int j = 1;j < t;j ++) cout << ' ';
        t --;
        for (int j = 1;j <= n;j ++)
        {
            f[i][j] = f[i-1][j]%2 + f[i-1][j+1]%2;
            f[i][j] %= 2;
        }
        bool flag = false;
        for (int j = 1;j <= n;j ++)
        {
            if (f[i][j] == 1) flag = true;
            if (f[i][j] == 1 || flag)
            {
                if ((i % 2 == 1) && f[i][j] == 1) cout << "/\\";
                if ((i % 2 == 0) && f[i][j] == 1)
                {
                    cout << "/__\\";
                    j ++;
                }
                if (!f[i][j]) cout << "  ";
            }
        }
        cout << endl;
    }
    return 0;
}


上一篇:20 公式求解


下一篇:Win11 vagrant up报错解决方案