摘要
Title: 889. 满足条件的01序列
Tag: 组合数、卡特兰数
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

889. 满足条件的01序列

• 题意

  给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。
  输出的答案对 10^9+7 取模。

• 思路

  

  证明写在之前的博客，link

  给出公式 卡特兰数

  $$Cat(n) = C(2n, n) - C(2n, n - 1) = \frac {C(2n, n)} {n + 1}$$

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-12 16:50:02
  FilePath: \ACM\Acwing\889.py
  LastEditTime: 2022-03-12 16:50:03
  '''
  
  
  def C(a, b):
      i, j, res = a, 1, 1
      while j <= b:
          res = res * i % MOD
          res = res * pow(j, MOD - 2, MOD) % MOD
          i -= 1
          j += 1
      return res
  
  
  MOD = int(1e9 + 7)
  n = int(input())
  print(C(2 * n, n) * pow(n + 1, MOD - 2, MOD) % MOD)