2 条题解
-
0
#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
#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
信息
- ID
- 1270
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 7
- 标签
- 递交数
- 233
- 已通过
- 48
- 上传者