QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#505707 | #7124. Binomial coefficient | 11d10xy | AC ✓ | 0ms | 3704kb | C++14 | 1.3kb | 2024-08-05 09:22:43 | 2024-08-05 09:22:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
using u32=unsigned;
using poly=array<u32,32>;
poly mul(poly f,poly g){
poly h{};
for(int i=0;i<32;i++)for(int j=0;i+j<32;j++)
h[i+j]+=f[i]*g[j];
return h;
}
inline i64 calc(poly f,u32 x){
u32 res=0;
for(int i=31;i>=0;i--)res=res*x+f[i];
return res;
}
u32 binom[32][32];
poly comp(poly f,u32 c){
poly g{};
u32 pw[32]{1};for(int i=1;i<32;i++)pw[i]=pw[i-1]*c;
for(int i=0;i<32;i++)for(int j=0;j<=i;j++)
g[j]+=f[i]*binom[i][j]*pw[i-j];
return g;
}
poly f[64];
inline i64 calct(i64 n){
i64 res=0;for(;n;res+=n/=2);
return res;
}
inline u32 inv(u32 x){
u32 r=1;for(int t=5;t--;r*=2-r*x);
return r;
}
u32 fac(i64 n){
u32 res=1;
for(;n;n/=2){
u32 w=0;
for(int i=63;i>=0;i--)if(n>>i&1)res*=calc(f[i],w),w+=1ull<<i;
}return res;
}
int main(){
for(int i=0;i<32;i++)binom[i][0]=1;
for(int i=1;i<32;i++)for(int j=1;j<32;j++)binom[i][j]=binom[i-1][j]+binom[i-1][j-1];
f[0]=f[1]={1,1};for(int i=2;i<64;i++){
f[i]=mul(f[i-1],comp(f[i-1],1ull<<i-1));
}
i64 n,m;cin>>n>>m;
i64 t=calct(n)-calct(m)-calct(n-m);u32 val=fac(n)*inv(fac(m))*inv(fac(n-m));
cout<<(t>=32?0:val<<t);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
4 2
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
1000000000 500000000
output:
4209467392
result:
ok 1 number(s): "4209467392"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
9 5
output:
126
result:
ok 1 number(s): "126"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
4 4
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 1
output:
4
result:
ok 1 number(s): "4"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
8 0
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
7 4
output:
35
result:
ok 1 number(s): "35"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
5 1
output:
5
result:
ok 1 number(s): "5"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
10 5
output:
252
result:
ok 1 number(s): "252"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
10 6
output:
210
result:
ok 1 number(s): "210"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
548 208
output:
550244848
result:
ok 1 number(s): "550244848"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
101 28
output:
3988840380
result:
ok 1 number(s): "3988840380"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
847 396
output:
111661020
result:
ok 1 number(s): "111661020"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
401 145
output:
4003233343
result:
ok 1 number(s): "4003233343"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
850 61
output:
541571168
result:
ok 1 number(s): "541571168"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
108 99
output:
2975642540
result:
ok 1 number(s): "2975642540"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
662 518
output:
1562442705
result:
ok 1 number(s): "1562442705"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
407 352
output:
1857174828
result:
ok 1 number(s): "1857174828"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
665 521
output:
3796194819
result:
ok 1 number(s): "3796194819"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
26 9
output:
3124550
result:
ok 1 number(s): "3124550"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
963837006 398758493
output:
2663079936
result:
ok 1 number(s): "2663079936"
Test #24:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
948507270 651192831
output:
1309671424
result:
ok 1 number(s): "1309671424"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
492986047 78933312
output:
2793371648
result:
ok 1 number(s): "2793371648"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
37464824 5920383
output:
181051392
result:
ok 1 number(s): "181051392"
Test #27:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
22135089 14539440
output:
3296657408
result:
ok 1 number(s): "3296657408"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
566613866 50184316
output:
3916726272
result:
ok 1 number(s): "3916726272"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
111092642 39294742
output:
569751552
result:
ok 1 number(s): "569751552"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
95762907 32448440
output:
2495508480
result:
ok 1 number(s): "2495508480"
Test #31:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
640241684 192946548
output:
1937432576
result:
ok 1 number(s): "1937432576"
Test #32:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
319645572 171079186
output:
2273689600
result:
ok 1 number(s): "2273689600"
Test #33:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
384118565739435739 279926992599854816
output:
0
result:
ok 1 number(s): "0"
Test #34:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
514630002561139050 342562804355107180
output:
2281701376
result:
ok 1 number(s): "2281701376"
Test #35:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
868513480532585464 620744630807193085
output:
0
result:
ok 1 number(s): "0"
Test #36:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
999024917354288774 174010839407941486
output:
0
result:
ok 1 number(s): "0"
Test #37:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
129536354175992084 40540657051530392
output:
2281701376
result:
ok 1 number(s): "2281701376"
Test #38:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
260047790997695395 184944531326445719
output:
1733853184
result:
ok 1 number(s): "1733853184"
Test #39:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
613931268969141809 232151379477837372
output:
0
result:
ok 1 number(s): "0"
Test #40:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
744442705790845119 697457906037415869
output:
0
result:
ok 1 number(s): "0"
Test #41:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
874954142612548430 747007213605125645
output:
0
result:
ok 1 number(s): "0"
Test #42:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
303530821616940606 71471793601986185
output:
0
result:
ok 1 number(s): "0"