QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#810293#3592. Leaving YharnamSGColinAC ✓51ms19572kbC++202.1kb2024-12-11 20:55:282024-12-11 20:55:34

Judging History

This is the latest submission verdict.

  • [2024-12-11 20:55:34]
  • Judged
  • Verdict: AC
  • Time: 51ms
  • Memory: 19572kb
  • [2024-12-11 20:55:28]
  • Submitted

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'