QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#34476 | #3592. Leaving Yharnam | caobao | AC ✓ | 494ms | 34960kb | C++17 | 3.2kb | 2022-06-09 19:22:41 | 2022-06-09 19:22:41 |
Judging History
answer
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
using namespace std;
ll pw(ll a, ll b)
{
if(a == 0) return 1;
if(b == 0) return 1;
ll res = pw(a * a % mod, b >> 1);
if(b&1) res = res * a % mod;
return res;
}
ll A[N * 2] {1};
ll invA[N * 2] {1};
void add(ll &a, ll b)
{
a += b%mod + mod;
a %= mod;
}
ll C(int a, int b)
{
if(b > a)return 0;
return A[a] * invA[b] % mod * invA[a - b] % mod;
}
int cnt(int sigle_seat, int pair_seat, int I, ll& num)
{
if(pair_seat >= I)
{
num = num * C(pair_seat, I) % mod * pw(2, I) % mod;
return I;
}
else
{
num = num * C(sigle_seat, min(I - pair_seat, sigle_seat)) % mod
* C(pair_seat, max(I - pair_seat - sigle_seat, 0)) % mod
* pw(2, pair_seat - max(I - pair_seat - sigle_seat, 0)) %mod;
return pair_seat - max(I - pair_seat - sigle_seat, 0);
}
}
// cnt for no G
int cnt2(int pair_seat, int I, int E, ll& num)
{
int ans = E;
num = num * C(pair_seat, E / 2) % mod;
if (E % 2 == 1)
{
ans--;
pair_seat -= E / 2;
E = 1;
}
else
{
pair_seat -= E / 2;
E = 0;
}
//2 3 1
if (I < pair_seat)
{
num = num * C(pair_seat, I + E) % mod * pw(2, I + E) % mod
* C(I + E , E) % mod;
ans += I;
}
else
{
// assert(pair_seat - E - max(I - pair_seat - E, 0))
num = num * C(pair_seat, E) % mod
* pw(2, E) % mod * C(pair_seat - E, max(I - pair_seat - E, 0)) % mod
* pw(2, pair_seat - E - max(I - pair_seat - E, 0)) % mod;
ans += E + pair_seat - (E + I - pair_seat);
}
return ans;
}
int main()
{
IOS
for(int i = 1; i < N * 2; i++)
{
A[i] = A[i - 1] * i % mod;
invA[i] = pw(A[i], mod - 2);
}
int n, g, i, e;
ll num;
cin >> n >> g >> i >> e;
if (g >= 2 * n)
{
g = 2 * n;
}
if(g + e >= 2 * n)
{
e = 2 * n - g;
}
if(g + i + e >= 2 * n)
{
i = 2 * n - g - e;
}
ll up = 0;
ll down = 0;
ll f = 0;
auto ff = [&](ll i)
{
int k = g - i;
return C(n, i) * C(i, k) % mod * pw(2, i - k) % mod * pw(C(2*n, g), mod - 2);
};
for(int k = g/2; k >= 0; k--)
{
// k pair easyG sit together
int sigleG = g - k * 2;
if(sigleG + k > n)continue;
int ans = g;
num = C(n, k) * C(n - k, sigleG) % mod * pw(sigleG, 2) % mod;
if(sigleG >= e)
{
ans += e;
num = num * C(sigleG, e) % mod;
ans += cnt(sigleG - e, n - k - sigleG, i, num);
}
else // sigleG < e
{
ans += sigleG;
ans += cnt2(n - sigleG - k, i, e - sigleG, num);
}
num = ff(g - k) % mod;
add(up, num * ans % mod);
add(down, num);
}
// num * p / down
cout << up * pw(down, mod - 2) % mod << endl;
// }
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 352ms
memory: 34804kb
input:
1 0 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 350ms
memory: 34792kb
input:
10 5 13 11
output:
16
result:
ok single line: '16'
Test #3:
score: 0
Accepted
time: 394ms
memory: 34688kb
input:
324005 203143 770973 565020
output:
648010
result:
ok single line: '648010'
Test #4:
score: 0
Accepted
time: 494ms
memory: 34796kb
input:
783794 966573 337313 49232
output:
658568709
result:
ok single line: '658568709'
Test #5:
score: 0
Accepted
time: 368ms
memory: 34824kb
input:
224046 630433 450997 667681
output:
448092
result:
ok single line: '448092'
Test #6:
score: 0
Accepted
time: 340ms
memory: 34868kb
input:
5 20 2 13
output:
10
result:
ok single line: '10'
Test #7:
score: 0
Accepted
time: 364ms
memory: 34828kb
input:
4 0 10 14
output:
8
result:
ok single line: '8'
Test #8:
score: 0
Accepted
time: 371ms
memory: 34892kb
input:
1 19 17 3
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 364ms
memory: 34824kb
input:
2 20 19 1
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 356ms
memory: 34896kb
input:
18 11 4 15
output:
30
result:
ok single line: '30'
Test #11:
score: 0
Accepted
time: 377ms
memory: 34820kb
input:
6 1 13 18
output:
12
result:
ok single line: '12'
Test #12:
score: 0
Accepted
time: 369ms
memory: 34808kb
input:
19 12 2 19
output:
32
result:
ok single line: '32'
Test #13:
score: 0
Accepted
time: 357ms
memory: 34852kb
input:
1 2 5 8
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 368ms
memory: 34804kb
input:
20 5 2 18
output:
24
result:
ok single line: '24'
Test #15:
score: 0
Accepted
time: 361ms
memory: 34688kb
input:
10 0 11 0
output:
9
result:
ok single line: '9'
Test #16:
score: 0
Accepted
time: 369ms
memory: 34832kb
input:
10 3 9 6
output:
11
result:
ok single line: '11'
Test #17:
score: 0
Accepted
time: 363ms
memory: 34824kb
input:
16 13 13 14
output:
27
result:
ok single line: '27'
Test #18:
score: 0
Accepted
time: 354ms
memory: 34692kb
input:
20 16 12 0
output:
153846178
result:
ok single line: '153846178'
Test #19:
score: 0
Accepted
time: 361ms
memory: 34836kb
input:
20 3 4 3
output:
10
result:
ok single line: '10'
Test #20:
score: 0
Accepted
time: 368ms
memory: 34836kb
input:
8 16 19 14
output:
16
result:
ok single line: '16'
Test #21:
score: 0
Accepted
time: 360ms
memory: 34852kb
input:
17 4 5 11
output:
19
result:
ok single line: '19'
Test #22:
score: 0
Accepted
time: 358ms
memory: 34824kb
input:
8 12 8 13
output:
16
result:
ok single line: '16'
Test #23:
score: 0
Accepted
time: 351ms
memory: 34896kb
input:
19 18 4 18
output:
36
result:
ok single line: '36'
Test #24:
score: 0
Accepted
time: 359ms
memory: 34896kb
input:
5 14 8 0
output:
10
result:
ok single line: '10'
Test #25:
score: 0
Accepted
time: 370ms
memory: 34892kb
input:
2 5 1 17
output:
4
result:
ok single line: '4'
Test #26:
score: 0
Accepted
time: 359ms
memory: 34820kb
input:
2 2 1 0
output:
333333338
result:
ok single line: '333333338'
Test #27:
score: 0
Accepted
time: 360ms
memory: 34892kb
input:
10 1 0 2
output:
2
result:
ok single line: '2'
Test #28:
score: 0
Accepted
time: 362ms
memory: 34848kb
input:
10 17 10 0
output:
17
result:
ok single line: '17'
Test #29:
score: 0
Accepted
time: 360ms
memory: 34896kb
input:
15 2 8 6
output:
16
result:
ok single line: '16'
Test #30:
score: 0
Accepted
time: 347ms
memory: 34840kb
input:
3 4 2 1
output:
5
result:
ok single line: '5'
Test #31:
score: 0
Accepted
time: 360ms
memory: 34800kb
input:
10 18 3 18
output:
20
result:
ok single line: '20'
Test #32:
score: 0
Accepted
time: 370ms
memory: 34836kb
input:
20 18 19 5
output:
23
result:
ok single line: '23'
Test #33:
score: 0
Accepted
time: 360ms
memory: 34900kb
input:
9 2 7 7
output:
11
result:
ok single line: '11'
Test #34:
score: 0
Accepted
time: 363ms
memory: 34836kb
input:
11 12 3 9
output:
21
result:
ok single line: '21'
Test #35:
score: 0
Accepted
time: 369ms
memory: 34836kb
input:
10 8 2 8
output:
18
result:
ok single line: '18'
Test #36:
score: 0
Accepted
time: 370ms
memory: 34804kb
input:
17 11 2 9
output:
22
result:
ok single line: '22'
Test #37:
score: 0
Accepted
time: 375ms
memory: 34752kb
input:
11 10 15 6
output:
16
result:
ok single line: '16'
Test #38:
score: 0
Accepted
time: 369ms
memory: 34960kb
input:
1 14 16 5
output:
2
result:
ok single line: '2'
Test #39:
score: 0
Accepted
time: 370ms
memory: 34748kb
input:
9 8 10 3
output:
11
result:
ok single line: '11'
Test #40:
score: 0
Accepted
time: 379ms
memory: 34888kb
input:
9 8 8 3
output:
11
result:
ok single line: '11'
Test #41:
score: 0
Accepted
time: 362ms
memory: 34824kb
input:
9 1 3 10
output:
13
result:
ok single line: '13'
Test #42:
score: 0
Accepted
time: 341ms
memory: 34752kb
input:
1000 500 0 0
output:
500
result:
ok single line: '500'
Test #43:
score: 0
Accepted
time: 362ms
memory: 34856kb
input:
1000 1000 0 0
output:
1000
result:
ok single line: '1000'
Test #44:
score: 0
Accepted
time: 357ms
memory: 34896kb
input:
1000 1500 0 0
output:
1500
result:
ok single line: '1500'
Test #45:
score: 0
Accepted
time: 368ms
memory: 34804kb
input:
1000 2000 0 0
output:
2000
result:
ok single line: '2000'
Test #46:
score: 0
Accepted
time: 351ms
memory: 34796kb
input:
1000 2500 0 0
output:
2000
result:
ok single line: '2000'
Test #47:
score: 0
Accepted
time: 362ms
memory: 34800kb
input:
1000 0 500 0
output:
500
result:
ok single line: '500'
Test #48:
score: 0
Accepted
time: 354ms
memory: 34892kb
input:
10 1 18 2
output:
3
result:
ok single line: '3'
Test #49:
score: 0
Accepted
time: 369ms
memory: 34836kb
input:
1000 0 1000 0
output:
1000
result:
ok single line: '1000'
Test #50:
score: 0
Accepted
time: 363ms
memory: 34960kb
input:
1000 0 1500 0
output:
500
result:
ok single line: '500'
Test #51:
score: 0
Accepted
time: 355ms
memory: 34792kb
input:
1000 0 2000 0
output:
0
result:
ok single line: '0'
Test #52:
score: 0
Accepted
time: 356ms
memory: 34800kb
input:
1000 0 2500 0
output:
0
result:
ok single line: '0'
Test #53:
score: 0
Accepted
time: 379ms
memory: 34892kb
input:
1000 0 0 500
output:
500
result:
ok single line: '500'
Test #54:
score: 0
Accepted
time: 373ms
memory: 34848kb
input:
1000 0 0 1000
output:
1000
result:
ok single line: '1000'
Test #55:
score: 0
Accepted
time: 358ms
memory: 34748kb
input:
1000 0 0 1500
output:
1500
result:
ok single line: '1500'
Test #56:
score: 0
Accepted
time: 368ms
memory: 34868kb
input:
1000 0 0 2000
output:
2000
result:
ok single line: '2000'
Test #57:
score: 0
Accepted
time: 369ms
memory: 34796kb
input:
1000 0 0 2500
output:
2000
result:
ok single line: '2000'
Test #58:
score: 0
Accepted
time: 360ms
memory: 34892kb
input:
1000 300 300 0
output:
600
result:
ok single line: '600'
Test #59:
score: 0
Accepted
time: 365ms
memory: 34840kb
input:
1 11 0 11
output:
2
result:
ok single line: '2'
Test #60:
score: 0
Accepted
time: 364ms
memory: 34896kb
input:
1000 500 500 0
output:
1000
result:
ok single line: '1000'
Test #61:
score: 0
Accepted
time: 363ms
memory: 34832kb
input:
1000 700 700 0
output:
158494380
result:
ok single line: '158494380'
Test #62:
score: 0
Accepted
time: 358ms
memory: 34836kb
input:
1000 1000 1000 0
output:
1000
result:
ok single line: '1000'
Test #63:
score: 0
Accepted
time: 371ms
memory: 34892kb
input:
1000 1500 1500 0
output:
1500
result:
ok single line: '1500'
Test #64:
score: 0
Accepted
time: 378ms
memory: 34800kb
input:
1000 2000 2000 0
output:
2000
result:
ok single line: '2000'
Test #65:
score: 0
Accepted
time: 378ms
memory: 34960kb
input:
1000 300 0 300
output:
600
result:
ok single line: '600'
Test #66:
score: 0
Accepted
time: 371ms
memory: 34720kb
input:
1000 500 0 500
output:
1000
result:
ok single line: '1000'
Test #67:
score: 0
Accepted
time: 359ms
memory: 34852kb
input:
1000 700 0 700
output:
1400
result:
ok single line: '1400'
Test #68:
score: 0
Accepted
time: 371ms
memory: 34868kb
input:
1000 1000 0 1000
output:
2000
result:
ok single line: '2000'
Test #69:
score: 0
Accepted
time: 366ms
memory: 34864kb
input:
1000 1500 0 1500
output:
2000
result:
ok single line: '2000'
Test #70:
score: 0
Accepted
time: 363ms
memory: 34804kb
input:
19 12 14 10
output:
24
result:
ok single line: '24'
Test #71:
score: 0
Accepted
time: 354ms
memory: 34692kb
input:
1000 2000 0 2000
output:
2000
result:
ok single line: '2000'
Test #72:
score: 0
Accepted
time: 367ms
memory: 34832kb
input:
1000 0 300 300
output:
600
result:
ok single line: '600'
Test #73:
score: 0
Accepted
time: 371ms
memory: 34804kb
input:
1000 0 500 500
output:
1000
result:
ok single line: '1000'
Test #74:
score: 0
Accepted
time: 353ms
memory: 34820kb
input:
1000 0 700 700
output:
1300
result:
ok single line: '1300'
Test #75:
score: 0
Accepted
time: 347ms
memory: 34896kb
input:
1000 0 1000 1000
output:
1000
result:
ok single line: '1000'
Test #76:
score: 0
Accepted
time: 359ms
memory: 34748kb
input:
1000 0 1500 1500
output:
1500
result:
ok single line: '1500'
Test #77:
score: 0
Accepted
time: 356ms
memory: 34836kb
input:
1000 0 2000 2000
output:
2000
result:
ok single line: '2000'
Test #78:
score: 0
Accepted
time: 351ms
memory: 34756kb
input:
2637 6773 9174 1735
output:
5274
result:
ok single line: '5274'
Test #79:
score: 0
Accepted
time: 378ms
memory: 34896kb
input:
2703 8304 3387 1641
output:
5406
result:
ok single line: '5406'
Test #80:
score: 0
Accepted
time: 367ms
memory: 34840kb
input:
6326 8700 3534 6848
output:
12652
result:
ok single line: '12652'
Test #81:
score: 0
Accepted
time: 359ms
memory: 34892kb
input:
15 15 12 17
output:
30
result:
ok single line: '30'
Test #82:
score: 0
Accepted
time: 350ms
memory: 34840kb
input:
2142 6609 4924 4096
output:
4284
result:
ok single line: '4284'
Test #83:
score: 0
Accepted
time: 360ms
memory: 34900kb
input:
9565 8872 6950 5722
output:
14594
result:
ok single line: '14594'
Test #84:
score: 0
Accepted
time: 359ms
memory: 34900kb
input:
547 2715 9932 9784
output:
1094
result:
ok single line: '1094'
Test #85:
score: 0
Accepted
time: 354ms
memory: 34748kb
input:
88 2600 8625 3878
output:
176
result:
ok single line: '176'
Test #86:
score: 0
Accepted
time: 335ms
memory: 34824kb
input:
1661 8169 2242 4146
output:
3322
result:
ok single line: '3322'
Test #87:
score: 0
Accepted
time: 363ms
memory: 34792kb
input:
4167 1089 8718 9606
output:
8334
result:
ok single line: '8334'
Test #88:
score: 0
Accepted
time: 355ms
memory: 34796kb
input:
4463 553 8538 5105
output:
5658
result:
ok single line: '5658'
Test #89:
score: 0
Accepted
time: 364ms
memory: 34848kb
input:
8142 9612 4922 8312
output:
16284
result:
ok single line: '16284'
Test #90:
score: 0
Accepted
time: 368ms
memory: 34800kb
input:
6612 6829 2173 4699
output:
11528
result:
ok single line: '11528'
Test #91:
score: 0
Accepted
time: 362ms
memory: 34868kb
input:
3435 7847 5234 2646
output:
6870
result:
ok single line: '6870'
Test #92:
score: 0
Accepted
time: 365ms
memory: 34956kb
input:
17 13 18 18
output:
31
result:
ok single line: '31'
Test #93:
score: 0
Accepted
time: 368ms
memory: 34912kb
input:
3425 9920 1367 7901
output:
6850
result:
ok single line: '6850'
Test #94:
score: 0
Accepted
time: 364ms
memory: 34960kb
input:
9741 9676 483 2051
output:
330597298
result:
ok single line: '330597298'
Test #95:
score: 0
Accepted
time: 367ms
memory: 34824kb
input:
2324 2737 5161 8088
output:
4648
result:
ok single line: '4648'
Test #96:
score: 0
Accepted
time: 363ms
memory: 34888kb
input:
6606 1493 824 9179
output:
11496
result:
ok single line: '11496'
Test #97:
score: 0
Accepted
time: 357ms
memory: 34852kb
input:
8265 9267 238 7595
output:
16530
result:
ok single line: '16530'
Test #98:
score: 0
Accepted
time: 359ms
memory: 34900kb
input:
6992 6132 164 5228
output:
11524
result:
ok single line: '11524'
Test #99:
score: 0
Accepted
time: 370ms
memory: 34792kb
input:
3647 6343 9074 4888
output:
7294
result:
ok single line: '7294'
Test #100:
score: 0
Accepted
time: 448ms
memory: 34820kb
input:
761933 965642 909762 628739
output:
1523866
result:
ok single line: '1523866'
Test #101:
score: 0
Accepted
time: 423ms
memory: 34868kb
input:
661992 436246 405301 690525
output:
1126771
result:
ok single line: '1126771'
Test #102:
score: 0
Accepted
time: 403ms
memory: 34800kb
input:
799120 245571 55209 777457
output:
1078237
result:
ok single line: '1078237'