1 条题解

  • 0
    @ 2025-10-8 17:09:18
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=1e4+10;
    const LL P=1e9;
    int n, m, pr, prime[N]; bool v[N]; 
    void init()
    {
    	pr=0; memset(v, 0, sizeof(v));
    	for(int i=2; i<=n+m; i++) 
    	{
    		if(v[i]==0) prime[++pr]=i;
    		for(int j=1; j<=pr && (i*prime[j]<=n+m); j++)
    		{
    			v[i*prime[j]]=1;
    			if(i%prime[j]==0) break;
    		}
    	}
    }
    struct node
    {
    	int len; LL a[2100];
    	node() {len=1; memset(a, 0, sizeof(a));}
    };
    node operator+(node n1, node n2)
    {
    	node no; no.len=max(n1.len, n2.len);
    	for(int i=1; i<=no.len; i++) no.a[i]=n1.a[i]+n2.a[i];
    	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 operator-(node n1, node n2)
    {
    	node no; no.len=max(n1.len, n2.len);
    	for(int i=1; i<=no.len; i++) no.a[i]=n1.a[i]-n2.a[i];
    	for(int i=1; i<=no.len; i++) if(no.a[i]<0)
    	{
    		no.a[i]+=P; no.a[i+1]--;
    	}
    	int i=no.len;
    	while(i>1 && no.a[i]==0) i--;
    	no.len=i;
    	return no;
    }
    node operator*(node n1, LL 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, int m)
    {
    	node ans; ans.a[1]=1; int M, cnt;
    	for(int i=1; i<=pr; i++)
    	{
    		if(prime[i]>n) break;
    		M=n; cnt=0;
    		while(M>0) M/=prime[i], cnt+=M;
    		M=m;
    		while(M>0) M/=prime[i], cnt-=M;
    		M=n-m;
    		while(M>0) M/=prime[i], cnt-=M;
    		while(cnt--) ans=ans*prime[i];
    	}
    	return ans;
    }
    void putnum(LL x)
    {
    	LL t=P/10;
    	while(x<t) printf("0"), t/=10;
    	printf("%d", x);
    }
    int main()
    {
    	scanf("%d%d", &n, &m); init();
    	node ans=C(n+m, m)-C(n+m, m-1);
    	printf("%lld", ans.a[ans.len]);
    	for(int i=ans.len-1; i>=1; i--) putnum(ans.a[i]);
    	printf("\n");
    	return 0;
    }
    • 1

    信息

    ID
    5572
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    递交数
    38
    已通过
    7
    上传者