QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#505707#7124. Binomial coefficient11d10xyAC ✓0ms3704kbC++141.3kb2024-08-05 09:22:432024-08-05 09:22:44

Judging History

你现在查看的是最新测评结果

  • [2024-08-05 09:22:44]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3704kb
  • [2024-08-05 09:22:43]
  • 提交

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"