2 条题解

  • 0
    @ 2025-10-8 17:07:04
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const LL P=1e9;
    const int N=1100;
    int pr, prime[N]; bool v[N];
    struct node
    {
        int len; LL a[N];
        node() {len=1; memset(a, 0, sizeof(a));}
    };
    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.a[1]=1; int cnt, M;
        for(int i=1; i<=pr; i++)
        {
            M=2*n; cnt=0;
            while(M>0) M/=prime[i], cnt+=M;
            M=n;
            while(M>0) M/=prime[i], cnt-=M;
            M=n+1;
            while(M>0) M/=prime[i], cnt-=M;
            while(cnt--) 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 17:06:57
      #include<bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      const LL P=1e9;
      const int N=1100;
      int pr, prime[N]; bool v[N];
      struct node
      {
      	int len; LL a[N];
      	node() {len=1; memset(a, 0, sizeof(a));}
      };
      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.a[1]=1; int cnt, M;
      	for(int i=1; i<=pr; i++)
      	{
      		M=2*n; cnt=0;
      		while(M>0) M/=prime[i], cnt+=M;
      		M=n;
      		while(M>0) M/=prime[i], cnt-=M;
      		M=n+1;
      		while(M>0) M/=prime[i], cnt-=M;
      		while(cnt--) 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数】[AHOI2012] 树屋阶梯

      信息

      ID
      4487
      时间
      1000ms
      内存
      128MiB
      难度
      6
      标签
      递交数
      81
      已通过
      27
      上传者