QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#810293 | #3592. Leaving Yharnam | SGColin | AC ✓ | 51ms | 19572kb | C++20 | 2.1kb | 2024-12-11 20:55:28 | 2024-12-11 20:55:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define N 2000007
#define mod 1000000007
int fac[N], ifac[N];
inline int fpow(int x, int t = mod - 2) {
int res = 1;
for (; t; t >>= 1, x = 1ll * x * x % mod)
if (t & 1) res = 1ll * res * x % mod;
return res;
}
inline void init() {
fac[0] = ifac[0] = 1;
for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[N - 1] = fpow(fac[N - 1], mod - 2);
for (int i = N - 2; i; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
}
inline int C(int n, int m) {
if (n < m) return 0;
return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int main() {
init();
int a = rd(), b = rd(), c = rd(), d = rd();
int n = a, g = b, i = c, e = d;
if (g >= 2 * n) {printf("%d\n", 2 * n); return 0;}
int dn = fpow(C(2 * n, g)), ans = 0;
for (int k = 0; k <= n; ++k) {
n = a, g = b, i = c, e = d;
int sig = g - 2 * k;
if (sig < 0 || sig > n - k) continue;
int p = 1ll * C(n, k) * C(n - k, sig) % mod * fpow(2, sig) % mod * dn % mod;
int toth = g;
int ept = n - k - sig;
bool fl = 0;
if (e <= sig) {
toth += e;
sig -= e;
} else {
toth += sig; e -= sig; sig = 0;
int w = min(e / 2, ept);
toth += w * 2; ept -= w; e -= w * 2;
if (e && ept) {--ept; ++sig; fl = 1;}
}
if (i <= ept) toth += i;
else {
i = max(0, i - ept);
if (i && fl) ++toth;
i = max(0, i - sig);
toth += max(ept - i, 0);
}
ans = (ans + 1ll * p * toth) % mod;
}
printf("%d\n", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 18ms
memory: 19384kb
input:
1 0 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 17ms
memory: 19460kb
input:
10 5 13 11
output:
16
result:
ok single line: '16'
Test #3:
score: 0
Accepted
time: 31ms
memory: 19376kb
input:
324005 203143 770973 565020
output:
648010
result:
ok single line: '648010'
Test #4:
score: 0
Accepted
time: 51ms
memory: 19452kb
input:
783794 966573 337313 49232
output:
658568709
result:
ok single line: '658568709'
Test #5:
score: 0
Accepted
time: 22ms
memory: 19384kb
input:
224046 630433 450997 667681
output:
448092
result:
ok single line: '448092'
Test #6:
score: 0
Accepted
time: 22ms
memory: 19448kb
input:
5 20 2 13
output:
10
result:
ok single line: '10'
Test #7:
score: 0
Accepted
time: 17ms
memory: 19376kb
input:
4 0 10 14
output:
8
result:
ok single line: '8'
Test #8:
score: 0
Accepted
time: 21ms
memory: 19448kb
input:
1 19 17 3
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 21ms
memory: 19380kb
input:
2 20 19 1
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 22ms
memory: 19456kb
input:
18 11 4 15
output:
30
result:
ok single line: '30'
Test #11:
score: 0
Accepted
time: 18ms
memory: 19384kb
input:
6 1 13 18
output:
12
result:
ok single line: '12'
Test #12:
score: 0
Accepted
time: 22ms
memory: 19400kb
input:
19 12 2 19
output:
32
result:
ok single line: '32'
Test #13:
score: 0
Accepted
time: 18ms
memory: 19376kb
input:
1 2 5 8
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 21ms
memory: 19452kb
input:
20 5 2 18
output:
24
result:
ok single line: '24'
Test #15:
score: 0
Accepted
time: 18ms
memory: 19456kb
input:
10 0 11 0
output:
9
result:
ok single line: '9'
Test #16:
score: 0
Accepted
time: 18ms
memory: 19392kb
input:
10 3 9 6
output:
11
result:
ok single line: '11'
Test #17:
score: 0
Accepted
time: 21ms
memory: 19452kb
input:
16 13 13 14
output:
27
result:
ok single line: '27'
Test #18:
score: 0
Accepted
time: 14ms
memory: 19376kb
input:
20 16 12 0
output:
153846178
result:
ok single line: '153846178'
Test #19:
score: 0
Accepted
time: 17ms
memory: 19448kb
input:
20 3 4 3
output:
10
result:
ok single line: '10'
Test #20:
score: 0
Accepted
time: 11ms
memory: 19444kb
input:
8 16 19 14
output:
16
result:
ok single line: '16'
Test #21:
score: 0
Accepted
time: 18ms
memory: 19440kb
input:
17 4 5 11
output:
19
result:
ok single line: '19'
Test #22:
score: 0
Accepted
time: 21ms
memory: 19388kb
input:
8 12 8 13
output:
16
result:
ok single line: '16'
Test #23:
score: 0
Accepted
time: 14ms
memory: 19448kb
input:
19 18 4 18
output:
36
result:
ok single line: '36'
Test #24:
score: 0
Accepted
time: 13ms
memory: 19508kb
input:
5 14 8 0
output:
10
result:
ok single line: '10'
Test #25:
score: 0
Accepted
time: 22ms
memory: 19568kb
input:
2 5 1 17
output:
4
result:
ok single line: '4'
Test #26:
score: 0
Accepted
time: 13ms
memory: 19452kb
input:
2 2 1 0
output:
333333338
result:
ok single line: '333333338'
Test #27:
score: 0
Accepted
time: 18ms
memory: 19376kb
input:
10 1 0 2
output:
2
result:
ok single line: '2'
Test #28:
score: 0
Accepted
time: 21ms
memory: 19448kb
input:
10 17 10 0
output:
17
result:
ok single line: '17'
Test #29:
score: 0
Accepted
time: 17ms
memory: 19444kb
input:
15 2 8 6
output:
16
result:
ok single line: '16'
Test #30:
score: 0
Accepted
time: 21ms
memory: 19444kb
input:
3 4 2 1
output:
5
result:
ok single line: '5'
Test #31:
score: 0
Accepted
time: 22ms
memory: 19384kb
input:
10 18 3 18
output:
20
result:
ok single line: '20'
Test #32:
score: 0
Accepted
time: 14ms
memory: 19384kb
input:
20 18 19 5
output:
23
result:
ok single line: '23'
Test #33:
score: 0
Accepted
time: 17ms
memory: 19504kb
input:
9 2 7 7
output:
11
result:
ok single line: '11'
Test #34:
score: 0
Accepted
time: 21ms
memory: 19380kb
input:
11 12 3 9
output:
21
result:
ok single line: '21'
Test #35:
score: 0
Accepted
time: 14ms
memory: 19456kb
input:
10 8 2 8
output:
18
result:
ok single line: '18'
Test #36:
score: 0
Accepted
time: 17ms
memory: 19400kb
input:
17 11 2 9
output:
22
result:
ok single line: '22'
Test #37:
score: 0
Accepted
time: 14ms
memory: 19420kb
input:
11 10 15 6
output:
16
result:
ok single line: '16'
Test #38:
score: 0
Accepted
time: 17ms
memory: 19440kb
input:
1 14 16 5
output:
2
result:
ok single line: '2'
Test #39:
score: 0
Accepted
time: 18ms
memory: 19444kb
input:
9 8 10 3
output:
11
result:
ok single line: '11'
Test #40:
score: 0
Accepted
time: 17ms
memory: 19568kb
input:
9 8 8 3
output:
11
result:
ok single line: '11'
Test #41:
score: 0
Accepted
time: 18ms
memory: 19452kb
input:
9 1 3 10
output:
13
result:
ok single line: '13'
Test #42:
score: 0
Accepted
time: 17ms
memory: 19456kb
input:
1000 500 0 0
output:
500
result:
ok single line: '500'
Test #43:
score: 0
Accepted
time: 14ms
memory: 19452kb
input:
1000 1000 0 0
output:
1000
result:
ok single line: '1000'
Test #44:
score: 0
Accepted
time: 14ms
memory: 19376kb
input:
1000 1500 0 0
output:
1500
result:
ok single line: '1500'
Test #45:
score: 0
Accepted
time: 22ms
memory: 19444kb
input:
1000 2000 0 0
output:
2000
result:
ok single line: '2000'
Test #46:
score: 0
Accepted
time: 18ms
memory: 19428kb
input:
1000 2500 0 0
output:
2000
result:
ok single line: '2000'
Test #47:
score: 0
Accepted
time: 18ms
memory: 19496kb
input:
1000 0 500 0
output:
500
result:
ok single line: '500'
Test #48:
score: 0
Accepted
time: 10ms
memory: 19500kb
input:
10 1 18 2
output:
3
result:
ok single line: '3'
Test #49:
score: 0
Accepted
time: 22ms
memory: 19448kb
input:
1000 0 1000 0
output:
1000
result:
ok single line: '1000'
Test #50:
score: 0
Accepted
time: 21ms
memory: 19384kb
input:
1000 0 1500 0
output:
500
result:
ok single line: '500'
Test #51:
score: 0
Accepted
time: 13ms
memory: 19436kb
input:
1000 0 2000 0
output:
0
result:
ok single line: '0'
Test #52:
score: 0
Accepted
time: 14ms
memory: 19448kb
input:
1000 0 2500 0
output:
0
result:
ok single line: '0'
Test #53:
score: 0
Accepted
time: 21ms
memory: 19380kb
input:
1000 0 0 500
output:
500
result:
ok single line: '500'
Test #54:
score: 0
Accepted
time: 18ms
memory: 19452kb
input:
1000 0 0 1000
output:
1000
result:
ok single line: '1000'
Test #55:
score: 0
Accepted
time: 18ms
memory: 19400kb
input:
1000 0 0 1500
output:
1500
result:
ok single line: '1500'
Test #56:
score: 0
Accepted
time: 21ms
memory: 19452kb
input:
1000 0 0 2000
output:
2000
result:
ok single line: '2000'
Test #57:
score: 0
Accepted
time: 18ms
memory: 19448kb
input:
1000 0 0 2500
output:
2000
result:
ok single line: '2000'
Test #58:
score: 0
Accepted
time: 11ms
memory: 19452kb
input:
1000 300 300 0
output:
600
result:
ok single line: '600'
Test #59:
score: 0
Accepted
time: 22ms
memory: 19456kb
input:
1 11 0 11
output:
2
result:
ok single line: '2'
Test #60:
score: 0
Accepted
time: 22ms
memory: 19448kb
input:
1000 500 500 0
output:
1000
result:
ok single line: '1000'
Test #61:
score: 0
Accepted
time: 22ms
memory: 19440kb
input:
1000 700 700 0
output:
158494380
result:
ok single line: '158494380'
Test #62:
score: 0
Accepted
time: 22ms
memory: 19428kb
input:
1000 1000 1000 0
output:
1000
result:
ok single line: '1000'
Test #63:
score: 0
Accepted
time: 11ms
memory: 19444kb
input:
1000 1500 1500 0
output:
1500
result:
ok single line: '1500'
Test #64:
score: 0
Accepted
time: 14ms
memory: 19360kb
input:
1000 2000 2000 0
output:
2000
result:
ok single line: '2000'
Test #65:
score: 0
Accepted
time: 17ms
memory: 19436kb
input:
1000 300 0 300
output:
600
result:
ok single line: '600'
Test #66:
score: 0
Accepted
time: 14ms
memory: 19456kb
input:
1000 500 0 500
output:
1000
result:
ok single line: '1000'
Test #67:
score: 0
Accepted
time: 17ms
memory: 19452kb
input:
1000 700 0 700
output:
1400
result:
ok single line: '1400'
Test #68:
score: 0
Accepted
time: 18ms
memory: 19368kb
input:
1000 1000 0 1000
output:
2000
result:
ok single line: '2000'
Test #69:
score: 0
Accepted
time: 13ms
memory: 19444kb
input:
1000 1500 0 1500
output:
2000
result:
ok single line: '2000'
Test #70:
score: 0
Accepted
time: 21ms
memory: 19452kb
input:
19 12 14 10
output:
24
result:
ok single line: '24'
Test #71:
score: 0
Accepted
time: 18ms
memory: 19432kb
input:
1000 2000 0 2000
output:
2000
result:
ok single line: '2000'
Test #72:
score: 0
Accepted
time: 14ms
memory: 19440kb
input:
1000 0 300 300
output:
600
result:
ok single line: '600'
Test #73:
score: 0
Accepted
time: 21ms
memory: 19408kb
input:
1000 0 500 500
output:
1000
result:
ok single line: '1000'
Test #74:
score: 0
Accepted
time: 14ms
memory: 19572kb
input:
1000 0 700 700
output:
1300
result:
ok single line: '1300'
Test #75:
score: 0
Accepted
time: 17ms
memory: 19436kb
input:
1000 0 1000 1000
output:
1000
result:
ok single line: '1000'
Test #76:
score: 0
Accepted
time: 21ms
memory: 19376kb
input:
1000 0 1500 1500
output:
1500
result:
ok single line: '1500'
Test #77:
score: 0
Accepted
time: 17ms
memory: 19384kb
input:
1000 0 2000 2000
output:
2000
result:
ok single line: '2000'
Test #78:
score: 0
Accepted
time: 13ms
memory: 19384kb
input:
2637 6773 9174 1735
output:
5274
result:
ok single line: '5274'
Test #79:
score: 0
Accepted
time: 14ms
memory: 19452kb
input:
2703 8304 3387 1641
output:
5406
result:
ok single line: '5406'
Test #80:
score: 0
Accepted
time: 21ms
memory: 19380kb
input:
6326 8700 3534 6848
output:
12652
result:
ok single line: '12652'
Test #81:
score: 0
Accepted
time: 21ms
memory: 19444kb
input:
15 15 12 17
output:
30
result:
ok single line: '30'
Test #82:
score: 0
Accepted
time: 22ms
memory: 19452kb
input:
2142 6609 4924 4096
output:
4284
result:
ok single line: '4284'
Test #83:
score: 0
Accepted
time: 14ms
memory: 19456kb
input:
9565 8872 6950 5722
output:
14594
result:
ok single line: '14594'
Test #84:
score: 0
Accepted
time: 17ms
memory: 19400kb
input:
547 2715 9932 9784
output:
1094
result:
ok single line: '1094'
Test #85:
score: 0
Accepted
time: 21ms
memory: 19448kb
input:
88 2600 8625 3878
output:
176
result:
ok single line: '176'
Test #86:
score: 0
Accepted
time: 18ms
memory: 19360kb
input:
1661 8169 2242 4146
output:
3322
result:
ok single line: '3322'
Test #87:
score: 0
Accepted
time: 21ms
memory: 19400kb
input:
4167 1089 8718 9606
output:
8334
result:
ok single line: '8334'
Test #88:
score: 0
Accepted
time: 18ms
memory: 19404kb
input:
4463 553 8538 5105
output:
5658
result:
ok single line: '5658'
Test #89:
score: 0
Accepted
time: 22ms
memory: 19452kb
input:
8142 9612 4922 8312
output:
16284
result:
ok single line: '16284'
Test #90:
score: 0
Accepted
time: 22ms
memory: 19444kb
input:
6612 6829 2173 4699
output:
11528
result:
ok single line: '11528'
Test #91:
score: 0
Accepted
time: 13ms
memory: 19376kb
input:
3435 7847 5234 2646
output:
6870
result:
ok single line: '6870'
Test #92:
score: 0
Accepted
time: 18ms
memory: 19432kb
input:
17 13 18 18
output:
31
result:
ok single line: '31'
Test #93:
score: 0
Accepted
time: 11ms
memory: 19440kb
input:
3425 9920 1367 7901
output:
6850
result:
ok single line: '6850'
Test #94:
score: 0
Accepted
time: 17ms
memory: 19392kb
input:
9741 9676 483 2051
output:
330597298
result:
ok single line: '330597298'
Test #95:
score: 0
Accepted
time: 14ms
memory: 19496kb
input:
2324 2737 5161 8088
output:
4648
result:
ok single line: '4648'
Test #96:
score: 0
Accepted
time: 13ms
memory: 19452kb
input:
6606 1493 824 9179
output:
11496
result:
ok single line: '11496'
Test #97:
score: 0
Accepted
time: 17ms
memory: 19444kb
input:
8265 9267 238 7595
output:
16530
result:
ok single line: '16530'
Test #98:
score: 0
Accepted
time: 18ms
memory: 19384kb
input:
6992 6132 164 5228
output:
11524
result:
ok single line: '11524'
Test #99:
score: 0
Accepted
time: 17ms
memory: 19400kb
input:
3647 6343 9074 4888
output:
7294
result:
ok single line: '7294'
Test #100:
score: 0
Accepted
time: 48ms
memory: 19500kb
input:
761933 965642 909762 628739
output:
1523866
result:
ok single line: '1523866'
Test #101:
score: 0
Accepted
time: 34ms
memory: 19448kb
input:
661992 436246 405301 690525
output:
1126771
result:
ok single line: '1126771'
Test #102:
score: 0
Accepted
time: 29ms
memory: 19512kb
input:
799120 245571 55209 777457
output:
1078237
result:
ok single line: '1078237'