QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#39974 | #3592. Leaving Yharnam | nidhs | AC ✓ | 330ms | 34920kb | C++ | 1.8kb | 2022-07-15 09:34:28 | 2022-07-15 09:34:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define inf 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
ll qow(ll a,ll p) {ll ans=1;for(;p;a=a*a%mod,p>>=1) if(p&1) ans=ans*a%mod;return ans;}
ll inv(ll a) {return qow(a,mod-2);}
const int N=2000010;
int T,n,a,b,c;
int ans;
int fac[N],invfac[N];
int C(int x,int y)
{
if(x<0||y<0||y>x) return 0;
return fac[x]*invfac[y]%mod*invfac[x-y]%mod;
}
int cal(int x)
{
int a1=a,b1=b,c1=c;
int ret=C(n,x)*C(n-x,a1-2*x)%mod*qow(2,a1-2*x)%mod*inv(C(2*n,a1))%mod;//概率
int bo=x;//两个均被占
int si=a1-2*x;//单个座位
int tot=a1;//贡献
if(si>=b1){
tot+=b1;
bo+=b1,si-=b1;
//剩下的是1
if(c1<=n-si-bo) tot+=c1;
else{
c1-=(n-si-bo),tot+=n-si-bo;
if(c1<=si) ;
else{
c1-=si;
c1=min(c1,n-si-bo);
tot-=c1;//原来c满意,现在不满意了
}
}
}
else{
//先跟a匹配
tot+=si,b1-=si,bo+=si,si=0;
//然后自己匹配
tot+=b1/2*2,bo+=b1/2,si=b1%2;
if(c1<=n-si-bo) tot+=c1;
else{
c1-=n-si-bo,tot+=n-si-bo;
if(c1<=si) tot+=c1;//c不满意,但是b满意了
else{
c1-=si;
tot+=si;//b满意了
c1=min(c1,n-si-bo);
tot-=c1;
}
}
}
//cout<<"|||"<<x<<' '<<ret<<' '<<tot<<'\n';
return ret*tot%mod;
}
signed main()
{
fac[0]=invfac[0]=1;
for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod,invfac[i]=inv(fac[i]);
cin>>n>>a>>c>>b;
if(a+b>=2*n){
cout<<2*n<<'\n';
return 0;
}
for(int i=0;i<=a/2;i++){//枚举有几个成对的
if(i+a-2*i>n) continue;
ans=(ans+cal(i))%mod;
}
int tot=0;
for(int i=0;i<=a/2;i++){
if(i+a-2*i>n) continue;
tot=(tot+C(n,i)*C(n-i,a-2*i)%mod*qow(2,a-2*i)%mod*inv(C(2*n,a))%mod)%mod;
}
assert(tot==1);
cout<<ans<<'\n';
}
/*
11 10 15 6
10 5 13 11
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 211ms
memory: 34780kb
input:
1 0 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 214ms
memory: 34784kb
input:
10 5 13 11
output:
16
result:
ok single line: '16'
Test #3:
score: 0
Accepted
time: 219ms
memory: 34780kb
input:
324005 203143 770973 565020
output:
648010
result:
ok single line: '648010'
Test #4:
score: 0
Accepted
time: 330ms
memory: 34768kb
input:
783794 966573 337313 49232
output:
658568709
result:
ok single line: '658568709'
Test #5:
score: 0
Accepted
time: 210ms
memory: 34872kb
input:
224046 630433 450997 667681
output:
448092
result:
ok single line: '448092'
Test #6:
score: 0
Accepted
time: 203ms
memory: 34784kb
input:
5 20 2 13
output:
10
result:
ok single line: '10'
Test #7:
score: 0
Accepted
time: 196ms
memory: 34780kb
input:
4 0 10 14
output:
8
result:
ok single line: '8'
Test #8:
score: 0
Accepted
time: 213ms
memory: 34916kb
input:
1 19 17 3
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 215ms
memory: 34860kb
input:
2 20 19 1
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 207ms
memory: 34688kb
input:
18 11 4 15
output:
30
result:
ok single line: '30'
Test #11:
score: 0
Accepted
time: 196ms
memory: 34764kb
input:
6 1 13 18
output:
12
result:
ok single line: '12'
Test #12:
score: 0
Accepted
time: 186ms
memory: 34916kb
input:
19 12 2 19
output:
32
result:
ok single line: '32'
Test #13:
score: 0
Accepted
time: 216ms
memory: 34920kb
input:
1 2 5 8
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 218ms
memory: 34916kb
input:
20 5 2 18
output:
24
result:
ok single line: '24'
Test #15:
score: 0
Accepted
time: 199ms
memory: 34748kb
input:
10 0 11 0
output:
9
result:
ok single line: '9'
Test #16:
score: 0
Accepted
time: 227ms
memory: 34836kb
input:
10 3 9 6
output:
11
result:
ok single line: '11'
Test #17:
score: 0
Accepted
time: 227ms
memory: 34752kb
input:
16 13 13 14
output:
27
result:
ok single line: '27'
Test #18:
score: 0
Accepted
time: 210ms
memory: 34836kb
input:
20 16 12 0
output:
153846178
result:
ok single line: '153846178'
Test #19:
score: 0
Accepted
time: 203ms
memory: 34844kb
input:
20 3 4 3
output:
10
result:
ok single line: '10'
Test #20:
score: 0
Accepted
time: 221ms
memory: 34784kb
input:
8 16 19 14
output:
16
result:
ok single line: '16'
Test #21:
score: 0
Accepted
time: 213ms
memory: 34772kb
input:
17 4 5 11
output:
19
result:
ok single line: '19'
Test #22:
score: 0
Accepted
time: 211ms
memory: 34848kb
input:
8 12 8 13
output:
16
result:
ok single line: '16'
Test #23:
score: 0
Accepted
time: 205ms
memory: 34780kb
input:
19 18 4 18
output:
36
result:
ok single line: '36'
Test #24:
score: 0
Accepted
time: 201ms
memory: 34840kb
input:
5 14 8 0
output:
10
result:
ok single line: '10'
Test #25:
score: 0
Accepted
time: 219ms
memory: 34768kb
input:
2 5 1 17
output:
4
result:
ok single line: '4'
Test #26:
score: 0
Accepted
time: 245ms
memory: 34736kb
input:
2 2 1 0
output:
333333338
result:
ok single line: '333333338'
Test #27:
score: 0
Accepted
time: 245ms
memory: 34656kb
input:
10 1 0 2
output:
2
result:
ok single line: '2'
Test #28:
score: 0
Accepted
time: 212ms
memory: 34860kb
input:
10 17 10 0
output:
17
result:
ok single line: '17'
Test #29:
score: 0
Accepted
time: 206ms
memory: 34840kb
input:
15 2 8 6
output:
16
result:
ok single line: '16'
Test #30:
score: 0
Accepted
time: 198ms
memory: 34840kb
input:
3 4 2 1
output:
5
result:
ok single line: '5'
Test #31:
score: 0
Accepted
time: 211ms
memory: 34768kb
input:
10 18 3 18
output:
20
result:
ok single line: '20'
Test #32:
score: 0
Accepted
time: 205ms
memory: 34660kb
input:
20 18 19 5
output:
23
result:
ok single line: '23'
Test #33:
score: 0
Accepted
time: 209ms
memory: 34784kb
input:
9 2 7 7
output:
11
result:
ok single line: '11'
Test #34:
score: 0
Accepted
time: 216ms
memory: 34768kb
input:
11 12 3 9
output:
21
result:
ok single line: '21'
Test #35:
score: 0
Accepted
time: 235ms
memory: 34660kb
input:
10 8 2 8
output:
18
result:
ok single line: '18'
Test #36:
score: 0
Accepted
time: 204ms
memory: 34748kb
input:
17 11 2 9
output:
22
result:
ok single line: '22'
Test #37:
score: 0
Accepted
time: 210ms
memory: 34676kb
input:
11 10 15 6
output:
16
result:
ok single line: '16'
Test #38:
score: 0
Accepted
time: 204ms
memory: 34784kb
input:
1 14 16 5
output:
2
result:
ok single line: '2'
Test #39:
score: 0
Accepted
time: 214ms
memory: 34772kb
input:
9 8 10 3
output:
11
result:
ok single line: '11'
Test #40:
score: 0
Accepted
time: 197ms
memory: 34764kb
input:
9 8 8 3
output:
11
result:
ok single line: '11'
Test #41:
score: 0
Accepted
time: 211ms
memory: 34872kb
input:
9 1 3 10
output:
13
result:
ok single line: '13'
Test #42:
score: 0
Accepted
time: 206ms
memory: 34744kb
input:
1000 500 0 0
output:
500
result:
ok single line: '500'
Test #43:
score: 0
Accepted
time: 207ms
memory: 34780kb
input:
1000 1000 0 0
output:
1000
result:
ok single line: '1000'
Test #44:
score: 0
Accepted
time: 216ms
memory: 34680kb
input:
1000 1500 0 0
output:
1500
result:
ok single line: '1500'
Test #45:
score: 0
Accepted
time: 210ms
memory: 34840kb
input:
1000 2000 0 0
output:
2000
result:
ok single line: '2000'
Test #46:
score: 0
Accepted
time: 207ms
memory: 34780kb
input:
1000 2500 0 0
output:
2000
result:
ok single line: '2000'
Test #47:
score: 0
Accepted
time: 201ms
memory: 34780kb
input:
1000 0 500 0
output:
500
result:
ok single line: '500'
Test #48:
score: 0
Accepted
time: 203ms
memory: 34740kb
input:
10 1 18 2
output:
3
result:
ok single line: '3'
Test #49:
score: 0
Accepted
time: 210ms
memory: 34752kb
input:
1000 0 1000 0
output:
1000
result:
ok single line: '1000'
Test #50:
score: 0
Accepted
time: 204ms
memory: 34784kb
input:
1000 0 1500 0
output:
500
result:
ok single line: '500'
Test #51:
score: 0
Accepted
time: 211ms
memory: 34768kb
input:
1000 0 2000 0
output:
0
result:
ok single line: '0'
Test #52:
score: 0
Accepted
time: 205ms
memory: 34764kb
input:
1000 0 2500 0
output:
0
result:
ok single line: '0'
Test #53:
score: 0
Accepted
time: 211ms
memory: 34840kb
input:
1000 0 0 500
output:
500
result:
ok single line: '500'
Test #54:
score: 0
Accepted
time: 210ms
memory: 34836kb
input:
1000 0 0 1000
output:
1000
result:
ok single line: '1000'
Test #55:
score: 0
Accepted
time: 199ms
memory: 34760kb
input:
1000 0 0 1500
output:
1500
result:
ok single line: '1500'
Test #56:
score: 0
Accepted
time: 208ms
memory: 34780kb
input:
1000 0 0 2000
output:
2000
result:
ok single line: '2000'
Test #57:
score: 0
Accepted
time: 207ms
memory: 34760kb
input:
1000 0 0 2500
output:
2000
result:
ok single line: '2000'
Test #58:
score: 0
Accepted
time: 211ms
memory: 34780kb
input:
1000 300 300 0
output:
600
result:
ok single line: '600'
Test #59:
score: 0
Accepted
time: 204ms
memory: 34872kb
input:
1 11 0 11
output:
2
result:
ok single line: '2'
Test #60:
score: 0
Accepted
time: 214ms
memory: 34844kb
input:
1000 500 500 0
output:
1000
result:
ok single line: '1000'
Test #61:
score: 0
Accepted
time: 211ms
memory: 34736kb
input:
1000 700 700 0
output:
158494380
result:
ok single line: '158494380'
Test #62:
score: 0
Accepted
time: 207ms
memory: 34916kb
input:
1000 1000 1000 0
output:
1000
result:
ok single line: '1000'
Test #63:
score: 0
Accepted
time: 214ms
memory: 34836kb
input:
1000 1500 1500 0
output:
1500
result:
ok single line: '1500'
Test #64:
score: 0
Accepted
time: 210ms
memory: 34868kb
input:
1000 2000 2000 0
output:
2000
result:
ok single line: '2000'
Test #65:
score: 0
Accepted
time: 216ms
memory: 34844kb
input:
1000 300 0 300
output:
600
result:
ok single line: '600'
Test #66:
score: 0
Accepted
time: 207ms
memory: 34780kb
input:
1000 500 0 500
output:
1000
result:
ok single line: '1000'
Test #67:
score: 0
Accepted
time: 212ms
memory: 34784kb
input:
1000 700 0 700
output:
1400
result:
ok single line: '1400'
Test #68:
score: 0
Accepted
time: 214ms
memory: 34920kb
input:
1000 1000 0 1000
output:
2000
result:
ok single line: '2000'
Test #69:
score: 0
Accepted
time: 208ms
memory: 34660kb
input:
1000 1500 0 1500
output:
2000
result:
ok single line: '2000'
Test #70:
score: 0
Accepted
time: 206ms
memory: 34920kb
input:
19 12 14 10
output:
24
result:
ok single line: '24'
Test #71:
score: 0
Accepted
time: 214ms
memory: 34680kb
input:
1000 2000 0 2000
output:
2000
result:
ok single line: '2000'
Test #72:
score: 0
Accepted
time: 208ms
memory: 34772kb
input:
1000 0 300 300
output:
600
result:
ok single line: '600'
Test #73:
score: 0
Accepted
time: 215ms
memory: 34780kb
input:
1000 0 500 500
output:
1000
result:
ok single line: '1000'
Test #74:
score: 0
Accepted
time: 203ms
memory: 34772kb
input:
1000 0 700 700
output:
1300
result:
ok single line: '1300'
Test #75:
score: 0
Accepted
time: 202ms
memory: 34844kb
input:
1000 0 1000 1000
output:
1000
result:
ok single line: '1000'
Test #76:
score: 0
Accepted
time: 205ms
memory: 34840kb
input:
1000 0 1500 1500
output:
1500
result:
ok single line: '1500'
Test #77:
score: 0
Accepted
time: 207ms
memory: 34752kb
input:
1000 0 2000 2000
output:
2000
result:
ok single line: '2000'
Test #78:
score: 0
Accepted
time: 208ms
memory: 34856kb
input:
2637 6773 9174 1735
output:
5274
result:
ok single line: '5274'
Test #79:
score: 0
Accepted
time: 208ms
memory: 34844kb
input:
2703 8304 3387 1641
output:
5406
result:
ok single line: '5406'
Test #80:
score: 0
Accepted
time: 214ms
memory: 34772kb
input:
6326 8700 3534 6848
output:
12652
result:
ok single line: '12652'
Test #81:
score: 0
Accepted
time: 204ms
memory: 34868kb
input:
15 15 12 17
output:
30
result:
ok single line: '30'
Test #82:
score: 0
Accepted
time: 212ms
memory: 34772kb
input:
2142 6609 4924 4096
output:
4284
result:
ok single line: '4284'
Test #83:
score: 0
Accepted
time: 214ms
memory: 34860kb
input:
9565 8872 6950 5722
output:
14594
result:
ok single line: '14594'
Test #84:
score: 0
Accepted
time: 219ms
memory: 34784kb
input:
547 2715 9932 9784
output:
1094
result:
ok single line: '1094'
Test #85:
score: 0
Accepted
time: 211ms
memory: 34784kb
input:
88 2600 8625 3878
output:
176
result:
ok single line: '176'
Test #86:
score: 0
Accepted
time: 204ms
memory: 34780kb
input:
1661 8169 2242 4146
output:
3322
result:
ok single line: '3322'
Test #87:
score: 0
Accepted
time: 212ms
memory: 34840kb
input:
4167 1089 8718 9606
output:
8334
result:
ok single line: '8334'
Test #88:
score: 0
Accepted
time: 207ms
memory: 34740kb
input:
4463 553 8538 5105
output:
5658
result:
ok single line: '5658'
Test #89:
score: 0
Accepted
time: 205ms
memory: 34716kb
input:
8142 9612 4922 8312
output:
16284
result:
ok single line: '16284'
Test #90:
score: 0
Accepted
time: 213ms
memory: 34868kb
input:
6612 6829 2173 4699
output:
11528
result:
ok single line: '11528'
Test #91:
score: 0
Accepted
time: 210ms
memory: 34772kb
input:
3435 7847 5234 2646
output:
6870
result:
ok single line: '6870'
Test #92:
score: 0
Accepted
time: 197ms
memory: 34772kb
input:
17 13 18 18
output:
31
result:
ok single line: '31'
Test #93:
score: 0
Accepted
time: 198ms
memory: 34680kb
input:
3425 9920 1367 7901
output:
6850
result:
ok single line: '6850'
Test #94:
score: 0
Accepted
time: 209ms
memory: 34660kb
input:
9741 9676 483 2051
output:
330597298
result:
ok single line: '330597298'
Test #95:
score: 0
Accepted
time: 212ms
memory: 34844kb
input:
2324 2737 5161 8088
output:
4648
result:
ok single line: '4648'
Test #96:
score: 0
Accepted
time: 199ms
memory: 34776kb
input:
6606 1493 824 9179
output:
11496
result:
ok single line: '11496'
Test #97:
score: 0
Accepted
time: 216ms
memory: 34760kb
input:
8265 9267 238 7595
output:
16530
result:
ok single line: '16530'
Test #98:
score: 0
Accepted
time: 216ms
memory: 34784kb
input:
6992 6132 164 5228
output:
11524
result:
ok single line: '11524'
Test #99:
score: 0
Accepted
time: 216ms
memory: 34768kb
input:
3647 6343 9074 4888
output:
7294
result:
ok single line: '7294'
Test #100:
score: 0
Accepted
time: 213ms
memory: 34836kb
input:
761933 965642 909762 628739
output:
1523866
result:
ok single line: '1523866'
Test #101:
score: 0
Accepted
time: 298ms
memory: 34772kb
input:
661992 436246 405301 690525
output:
1126771
result:
ok single line: '1126771'
Test #102:
score: 0
Accepted
time: 253ms
memory: 34780kb
input:
799120 245571 55209 777457
output:
1078237
result:
ok single line: '1078237'