QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#39974#3592. Leaving YharnamnidhsAC ✓330ms34920kbC++1.8kb2022-07-15 09:34:282022-07-15 09:34:30

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-15 09:34:30]
  • Judged
  • Verdict: AC
  • Time: 330ms
  • Memory: 34920kb
  • [2022-07-15 09:34:28]
  • Submitted

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'