2 条题解

  • 0
    @ 2025-10-8 16:55:57
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const LL P = 1e8;
    const int N = 6e4 + 10;
    int pr, prime[N]; bool v[2 * N];
    struct node {
        int len; LL a[5000];
    };
    void init(int n) {
        pr = 0; memset(v, 0, sizeof(v));
        for (int i = 2; i <= n; i++) {
            if (v[i] == 0) prime[++pr] = i;
            for (int j = 1; j <= pr && (i * prime[j] <= n); j++) {
                v[i * prime[j]] = 1;
                if (i % prime[j] == 0) break;
            }
        }
    }
    node operator*(node n1, int x) {
        node no; no.len = n1.len;
        for (int i = 1; i <= no.len; i++) no.a[i] = n1.a[i] * x;
        for (int i = 1; i <= no.len; i++) {
            no.a[i + 1] += no.a[i] / P;
            no.a[i] %= P;
        }
        int i = no.len;
        while (no.a[i + 1] > 0) {
            i++;
            no.a[i + 1] += no.a[i] / P;
            no.a[i] %= P;
        }
        while (i > 1 && no.a[i] == 0) i--;
        no.len = i;
        return no;
    }
    node C(int n) {
        node res; res.len = 1; res.a[1] = 1;
        for (int i = 1; i <= pr; i++) {
            int M = 2 * n, t = 0;
            while (M > 0) M /= prime[i], t += M;
            M = n;
            while (M > 0) M /= prime[i], t -= M;
            M = n + 1;
            while (M > 0) M /= prime[i], t -= M;
            while (t--) res = res * prime[i];
        }
        return res;
    }
    void putnum(int x) {
        int t = P / 10;
        while (x < t) printf("0"), t /= 10;
        printf("%d", x);
    }
    int main() {
        int n; scanf("%d", &n); init(2 * n);
        node ans = C(n);
        printf("%lld", ans.a[ans.len]);
        for (int i = ans.len - 1; i >= 1; i--) putnum(ans.a[i]);
        printf("\n");
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:55:46
      #include<bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      const LL P=1e8;
      const int N=6e4+10;
      int pr, prime[N]; bool v[2*N];
      struct node
      {
          int len; LL a[5000];
      };
      void init(int n)
      {
          pr=0; memset(v, 0, sizeof(v));
          for(int i=2; i<=n; i++)
          {
              if(v[i]==0) prime[++pr]=i;
              for(int j=1; j<=pr && (i*prime[j]<=n); j++)
              {
                  v[i*prime[j]]=1;
                  if(i%prime[j]==0) break;
              }
          }
      }
      node operator*(node n1, int x)
      {
          node no; no.len=n1.len;
          for(int i=1; i<=no.len; i++) no.a[i]=n1.a[i]*x;
          for(int i=1; i<=no.len; i++)
          {
              no.a[i+1]+=no.a[i]/P;
              no.a[i]%=P;
          }
          int i=no.len;
          while(no.a[i+1]>0)
          {
              i++;
              no.a[i+1]+=no.a[i]/P;
              no.a[i]%=P;
          }
          while(i>1 && no.a[i]==0) i--;
          no.len=i;
          return no; 
      }
      node C(int n)
      {
          node res; res.len=1;res.a[1]=1;
          for(int i=1; i<=pr; i++)
          {
              int M=2*n,t=0;
              while(M>0) M/=prime[i], t+=M;
              M=n;
              while(M>0) M/=prime[i], t-=M;
              M=n+1;
              while(M>0) M/=prime[i], t-=M;
              while(t--) res=res*prime[i];
          }
          return res;
      }
      void putnum(int x)
      {
          int t=P/10;
          while(x<t) printf("0"), t/=10;
          printf("%d", x);
      }
      int main()
      {
          int n; scanf("%d", &n); init(2*n);
          node ans=C(n);
          printf("%lld", ans.a[ans.len]);
          for(int i=ans.len-1; i>=1; i--) putnum(ans.a[i]);
          printf("\n");
          return 0;
      }
      • 1

      *【组合数:Catalan数】火车进出栈问题[NOIP普及组2003数据加强版]

      信息

      ID
      1270
      时间
      1000ms
      内存
      64MiB
      难度
      7
      标签
      递交数
      233
      已通过
      48
      上传者