B.牛牛和网格三角形

Powered by:AB_IN 局外人

B. 牛牛和网格三角形

先引进一下卡特兰数的概念：

卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为（从第零项开始） : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

其实这个题，大佬一眼就能看出来，这个题无非就是卡特兰数通项公式推导的几何呈现。

通项公式 ：

递归公式 ：
$$

递推公式 ：
$n+1 == 2 ^ k (k \in 0,1,2……)\frac{1}{n+1}C_{2n}^n$为奇数的充要条件，然后就判断就行了。

好的，以上就是大佬的解题方案（与我无瓜）。
——————————————————————————————————

那我们就简单推导一下卡特兰数的通项公式

首先引进一个经典问题：

• 一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?

看到这个题，脑海里第一个冒出来的限定条件应该是: 出栈的次数不能大于入栈的次数。凭空想象也想不出来怎么约束，那就万能画图法，以轴作为入栈次数，以轴作为出栈次数。

如图：

• 红线为，当时，假设线段为一条途径从

我们前头说了， 出栈的次数不能大于入栈的次数，那么转换成数学公式就是: ，换个方式来讲，就是在直线的下方，即红线下方。
显然，蓝色的是符合条件的一条路径，而橙色的是不符合条件的一条途径。
看到这，你应该就看出来了，下三角形就是这个题。

那么，怎么求得上每个整数点所对应的符合条件的路径条数呢？

比较好想的方法就是，我们可不可以从全部路径中，减去不符合的路径条数？
显然是可以的。

那么首先，全部路径怎么求？

• 当只能往上或往往右走，求从零点到达第一象限的某个整数点的路径条数。 这貌似是一个很经典的入门题了，核心思想就是:$$
  如图：

  • 我们所需要的数列就是

    好了，我们懂了怎么推出来数列，但只是会递推，这没有公式可咋整？
    这时候就可以搬出本篇文章的主角——组合数

    其实你肯定能想到，（挑选 + 没有顺序），这就是组合数的应用条件。怎么到达这个点，无非就是往上走四步，往右走四步，然后随意组合罢了。那么，这不就是嘛？那么宏观来看，公式就是。

好了，解决完全部路径，就该算不符合的了。

• 不符合的满足什么条件呢？显而易见就是超出了这条红线，换种说法，就是 **直线上和直线上面的整数点。**

  如图：

  • 橙色线为不符合途径，黑色线为，红色线为

    
    那我们怎么求这些不符合条件的路径的条数呢？

    这里就用到了一个非常巧妙的方法——转换法

    什么意思呢？就是将这条路线转换成另一条路线，即等效为另一条路线。**把第一次碰到该以后的部分关于对称。** 这样这条路线就会到达另一个终点，就可以计算到达这个终点的路径的条数了！（即我们需要求的不符合的路径条数）

    如图：

  • 紫色虚线即为 第一次碰到该以后的部分关于对称后的部分。
    

    那么很清晰的看到终点G的坐标为，到达的路径有多少条呢？即。那么宏观来看，公式就是。（也可以是）

好，我们现在做的，就是相减咯！

求出卡特兰数，一切就迎刃而解了…………然后乱推就可以推出来了。

怎么乱 推呢？
先化简结论吧！
$\frac{[1×3……×(2n - 1)] ×(2^n)}{(n+1)!}$的奇偶即可！

• 首先观察，一定是奇数，那就看的奇偶。
  如果要为偶数，那么就是问 **里的的因子个数是否小于**。

问题再一次转化了，首先我们需要会**求的的因子个数。**（就是将素因子分解了，求这一项的指数）

• 最简单的思路就是按贡献来算，是只贡献了一个的个数，也是里有多少个偶数，每个偶数先提供个；是贡献了两个的个数，就是的倍数还可以提供一个……

• 那么的因子个数为$$

• 给出不等式

  

  将带进去一看

  

  正好成立！

  • 所以当是的幂的时候，的因子个数为，同时也验证一件事，**的的因子个数最大就是**
  • 那么当不是的幂的时候，那么由于向下取整，肯定会有损失，所以是小于。

回到这个题，我们知道最多有个的因子，只有当且仅当为的幂时。这样就分两种情况了：

• 有个的因子，正好与分子的约掉，然后这个式子就为奇数。
• 没有个的因子，那就有的约不掉，那这个式子就为偶数。

我不会乱推怎么办！！！

当然，打表真香。
写出卡特兰数公式，打表！

class Solution:
    def judge(self , n ):
        # write code here
        n = int(n)
        import math
        ans = math.factorial(2 * n) // (math.factorial(n) * math.factorial(n + 1))
        return ans & 1
for _ in range(1, 100):
    print(Solution().judge(_), end = " ")

出来结果：

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

我们提取，也就是的位置，得到这样一个数列，这打眼一看，就是鸭！所以就判断是不是即可。

不会判断！！

代码扔给你

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @param n string字符串 三角形的长和高
# @return bool布尔型
#
class Solution:
    def judge(self , n ):
        # write code here
        n = int(n)
        import math
        return bin(n + 1)[3:].count("1") == 0

或者

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @param n string字符串 三角形的长和高
# @return bool布尔型
#
class Solution:
    def judge(self , n ):
        # write code here
        n = int(n)
        import math
        return n & (n + 1) == 0

你肯定懂的！

完结。