B.牛牛和网格三角形

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, ...

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

通项公式 ：

$h[n]=\frac{1}{n+1}C_{2n}^n$

递归公式 ：
$ $h[0]=1$ $h[1]=1$ $h[n]=h[0]∗h[n−1]+h[1]∗h[n−2]+...+h[n−1]∗h[0](n>=2)$ $

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

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

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

首先引进一个经典问题：

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

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

如图：

红线为 $y=x$ ，当 $n = 4$ 时，假设线段 $ABC$ 为一条途径从 $(0,0) -> (4,4)$

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

那么，怎么求得 $y = x$ 上每个整数点所对应的符合条件的路径条数呢？
在这里插入图片描述
比较好想的方法就是，我们可不可以从全部路径中，减去不符合的路径条数？
显然是可以的。

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

当只能往上或往往右走，求从零点到达第一象限的某个整数点的路径条数。 这貌似是一个很经典的 $dp$ 入门题了，核心思想就是:$ $一个点的路径条数=它左边的路径条数 + 它下面的路径条数$ $
如图：
- 我们所需要的数列就是 $1,2,6,20,70……$
  
  好了，我们懂了怎么推出来数列，但只是会递推，这没有公式可咋整？
  这时候就可以搬出本篇文章的主角——组合数
  
  其实你肯定能想到，（挑选 + 没有顺序），这就是组合数的应用条件。怎么到达 $(4,4)$ 这个点，无非就是往上走四步，往右走四步，然后随意组合罢了。那么，这不就是 $C_{8}^4$ 嘛？那么宏观来看，公式就是 $C_{2n}^n$ 。

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

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

如图：
- 橙色线 $ABCD$ 为不符合途径，黑色线为 $y = x + 1$ ，红色线为 $y = x$
  
  那我们怎么求这些不符合条件的路径的条数呢？
  
  这里就用到了一个非常巧妙的方法——转换法
  
  什么意思呢？就是将这条路线转换成另一条路线，即等效为另一条路线。**把第一次碰到该 $y = x + 1$ 以后的部分关于 $y = x + 1$ 对称。** 这样这条路线就会到达另一个终点，就可以计算到达这个终点的路径的条数了！（即我们需要求的不符合的路径条数）
  
  如图：
- 紫色虚线即为第一次碰到该 $y = x + 1$ 以后的部分关于 $y = x + 1$ 对称后的部分。
  
  那么很清晰的看到终点G的坐标为 $(3,5)$ ，到达 $(3,5)$ 的路径有多少条呢？即 $C_{8}^5$ 。那么宏观来看，公式就是 $C_{2n}^{n + 1}$ 。（也可以是 $C_{2n}^{n - 1}$ ）

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

$\begin{aligned} Catalan_n&=C_{2n}^n-C_{2n}^{n+1}\\ &=\frac{(2n)!}{n!n!}-\frac{(2n)!}{(n+1)!(n-1)!}\\ &=\frac{1}{n+1}(\frac{(2n)!(n+1)}{n!n!}-\frac{(2n)!}{n!(n-1)!})\\ &=\frac{1}{n+1}(\frac{(2n)!(n+1)}{n!*n!}-\frac{(2n)!n}{n!n!})\\ &=\frac{1}{n+1}\frac{(2n)!(n+1)-(2n)!*n}{n!n!}\\ &=\frac{1}{n+1}\frac{(2n)!}{n!*n!}\\ &=\frac{1}{n+1}C_{2n}^n\\ \end{aligned}$

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

怎么乱推呢？
先化简结论吧！
$ $\begin{aligned} Catalan_n&=\frac{1}{n+1}C_{2n}^n \\ &= \frac{(2n)!}{n!n!}×\frac{1}{n+1} \\ &= \frac{1×2×3×4……×(2n)}{n!n!}×\frac{1}{n+1}\\ &=\frac{[1×3……×(2n - 1)] ×[2×(2·2)×(2·3)×……×(2·n)]}{n!n!}×\frac{1}{n+1}\\ &=\frac{[1×3……×(2n - 1)] ×(2^n×n!)}{n!n!}×\frac{1}{n+1}\\ &=\frac{[1×3……×(2n - 1)] ×(2^n)}{(n+1)!}\\ \end{aligned}$ $所以就判断$ \frac{[1×3……×(2n - 1)] ×(2^n)}{(n+1)!}$的奇偶即可！

首先观察， $1×3……×(2n - 1)$ 一定是奇数，那就看 $f(n) = \frac{2^n} {(n+1)!}$ 的奇偶。
如果要 $f(n)$ 为偶数，那么就是问 ** $(n+1)!$ 里的 $2$ 的因子个数是否小于 $n$ **。

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

最简单的思路就是按贡献来算， $\lfloor \frac{n} {2} \rfloor$ 是只贡献了一个 $2$ 的个数，也是 $n!$ 里有多少个偶数，每个偶数先提供个 $2$ ； $\lfloor \frac{n} {4} \rfloor$ 是贡献了两个 $2$ 的个数，就是 $4$ 的倍数还可以提供一个 $2$ ……
那么 $2$ 的因子个数为$ $\lfloor \frac{n} {2} \rfloor + \lfloor \frac{n} {4} \rfloor + \lfloor \frac{n} {8} \rfloor + \lfloor \frac{n} {16} \rfloor+ ……$ $
给出不等式

将 $n = 2^n$ 带进去一看

正好成立！
- 所以当 $n$ 是 $2$ 的幂的时候， $2$ 的因子个数为 $n-1$ ，同时也验证一件事，** $n!$ 的 $2$ 的因子个数最大就是 $n-1$ **
- 那么当 $n$ 不是 $2$ 的幂的时候，那么由于向下取整，肯定会有损失，所以是小于。

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

$(n+1)!$ 有 $n$ 个 $2$ 的因子，正好与分子的 $2^n$ 约掉，然后这个式子 $\frac{2^n} {(n+1)!}$ 就为奇数。
$(n+1)!$ 没有 $n$ 个 $2$ 的因子，那就有的 $2$ 约不掉，那这个式子就为偶数。

~~我不会乱推怎么办！！！~~

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

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

我们提取 $True$ ，也就是 $1$ 的位置，得到这样一个数列 $1,3,7,15……$ ，这打眼一看，就是 $2^n - 1$ 鸭！所以就判断 $n+1$ 是不是 $2^k$ 即可。

~~不会判断！！~~

代码扔给你

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @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

你肯定懂的！

完结。