QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#34476#3592. Leaving YharnamcaobaoAC ✓494ms34960kbC++173.2kb2022-06-09 19:22:412022-06-09 19:22:41

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-06-09 19:22:41]
  • Judged
  • Verdict: AC
  • Time: 494ms
  • Memory: 34960kb
  • [2022-06-09 19:22:41]
  • Submitted

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'