卡特兰数

定义：长度为n，且由0和1组成的字符串，满足任意前缀中0的个数不小于1的个数的方法数。
公式：

经典问题
火车进出站的方案数（这道题由于数据范围过大，用了质因子分解的方法，本质是卡特兰数）

  1. // 卡特兰数：C(2n, n) / (n + 1)
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  6. typedef long long int64;
  8. const int N = 6000000, M = 1e9;
  10. int64 a[N];
  11. int tt = 0;
  12. bool st[60010 * 2];
  13. int p[60010 * 2];
  15. void out() {
  16.     for(int i = tt - 1; i >= 0; i--) {
  17.         if(i == tt - 1) {
  18.             printf("%lld", a[i]);
  19.         }
  20.         else {
  21.             printf("%09lld", a[i]);
  22.         }
  23.     }
  24.     printf("\n");
  25. }
  27. void multi(int prime) {
  28.     int64 t = 0;
  29.     for(int i = 0; i < tt; i++) {
  30.         t += a[i] * prime;
  31.         a[i] = t % M;
  32.         t /= M;
  33.     }
  34.     while(t) {
  35.         a[tt++] = t % M;
  36.         t /= M;
  37.     }
  38. }
  40. int get(int64 num, int prime) {
  41.     int ans = 0;
  42.     while(num) {
  43.         ans += num / prime;
  44.         num /= prime;
  45.     }
  46.     return ans;
  47. }
  49. int main() {
  50.     memset(st, 0, sizeof st);
  51.     memset(p, 0, sizeof p);
  52.     memset(a, 0, sizeof a);
  54.     int n;
  55.     scanf("%d", &n);
  57.     for(int i = 2; i <= 2 * n; i ++) {
  58.         if(st[i]) {
  59.             continue;
  60.         }
  61.         for(int j = i * 2; j <= 2 * n; j += i) {
  62.             st[j] = true;
  63.         }
  64.     }
  66.     for(int i = 2; i <= 2 * n; i++) {
  67.         if(!st[i]) {
  68.             p[i] = get(2 * n, i) - get(n, i) * 2;
  69.         }
  70.     }
  72.     int k = n + 1;
  73.     for(int i = 2; i <= k; i++) {
  74.         if(!st[i]) {
  75.             while(k % i == 0) {
  76.                 k /= i;
  77.                 p[i]--;
  78.             }
  79.         }
  80.     }
  82.     a[tt++] = 1;
  83.     for(int i = 2; i <= 2 * n; i++) {
  84.         //if(p[i]) printf("p[%d]: %d\n", i, p[i]);
  85.         while(p[i]) {
  86.             multi(i);
  87.             p[i]--;
  88.         }
  89.     }
  91.     out();
  93.     return 0;
  94. }