1 条题解
-
0
#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
- 上传者