QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397988 | #3751. 组合数 | xlwang# | AC ✓ | 36ms | 15164kb | C++14 | 1.8kb | 2024-04-24 21:00:43 | 2024-04-24 21:00:44 |
Judging History
answer
#include<bits/stdc++.h>
#define int __int128
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
#define foredge(i,j) for(register int i=head[j];i;i=e[i].nxt)
#define pb push_back
#define Times printf("Time:%.3lf\n",clock()/CLOCKS_PER_SEC)
using namespace std;
inline int read(){
int x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return f?-x:x;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void writeln(int x){write(x); puts("");}
inline void writepl(int x){write(x); putchar(' ');}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int randfind(int l,int r){return rnd()%(r-l+1)+l;}
//inline void init(){
// int t=read();
// while(t--) work();
//}
const int inf=1e18;
long long a,b;
int n,m;
int C[1010][1010];
inline void work(){
n=a,m=b;
if(m==0){
writeln(1);
return;
}
if(n<=1000){
writeln(C[n][m]);
return;
}
if(m>10){
writeln(inf);
return;
}
int ans=1,num1=n,num2=1;
fr(i,1,m){
ans=ans*num1/num2;
--num1,++num2;
if(ans>inf){
writeln(inf);
return;
}
}
if(ans>inf) writeln(inf);
else writeln(ans);
}
inline void init(){
C[0][0]=1;
int N=1e3;
fr(i,1,N){
C[i][0]=1;
fr(j,1,i) C[i][j]=min(C[i-1][j]+C[i-1][j-1],inf);
}
while(scanf("%lld%lld",&a,&b)!=EOF) work();
}
signed main(){
// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
init();
// printf("\nTIME:%.3lf",(double)clock()/CLOCKS_PER_SEC);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 36ms
memory: 15164kb
input:
1 0 1 1 2 0 2 1 2 2 3 0 3 1 3 2 3 3 4 0 4 1 4 2 4 3 4 4 5 0 5 1 5 2 5 3 5 4 5 5 6 0 6 1 6 2 6 3 6 4 6 5 6 6 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 8 0 8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8 9 0 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 10 0 10 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 11 0 11 1 11 2 11 3 11 4 11 ...
output:
1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 ...
result:
ok 100000 tokens