제출 #1227812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227812		jasonic	Boat (APIO16_boat)	C++20	58 / 100	2093 ms	12332 KiB

boat

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

const ll MOD = 1e9 + 7;

// a little birdie told me this is the best way to write code
const ll inv[501] = {0, 1, 500000004, 333333336, 250000002, 400000003, 166666668, 142857144, 125000001, 111111112, 700000005, 818181824, 83333334, 153846155, 71428572, 466666670, 562500004, 352941179, 55555556, 157894738, 850000006, 47619048, 409090912, 739130440, 41666667, 280000002, 576923081, 370370373, 35714286, 758620695, 233333335, 129032259, 281250002, 939393946, 676470593, 628571433, 27777778, 621621626, 78947369, 717948723, 425000003, 658536590, 23809524, 395348840, 204545456, 822222228, 369565220, 404255322, 520833337, 448979595, 140000001, 784313731, 788461544, 56603774, 685185190, 763636369, 17857143, 385964915, 879310351, 50847458, 616666671, 688524595, 564516133, 15873016, 140625001, 30769231, 469696973, 686567169, 838235300, 579710149, 814285720, 98591550, 13888889, 410958907, 310810813, 93333334, 539473688, 831168837, 858974365, 202531647, 712500005, 123456791, 329268295, 84337350, 11904762, 670588240, 197674420, 252873565, 102272728, 415730340, 411111114, 164835166, 184782610, 43010753, 202127661, 231578949, 760416672, 268041239, 724489801, 646464651, 570000004, 940594066, 892156869, 572815538, 394230772, 209523811, 28301887, 224299067, 342592595, 9174312, 881818188, 873873880, 508928575, 893805316, 692982461, 147826088, 939655179, 239316241, 25423729, 478991600, 808333339, 438016532, 844262301, 886178868, 782258070, 856000006, 7936508, 480314964, 570312504, 798449618, 515384619, 190839696, 734848490, 165413535, 843283588, 274074076, 419117650, 58394161, 789855078, 604316551, 407142860, 134751774, 49295775, 832167838, 506944448, 151724139, 705479457, 149659865, 655405410, 530201346, 46666667, 483443712, 269736844, 594771246, 915584422, 625806456, 929487186, 343949047, 601265827, 685534596, 856250006, 962732926, 561728399, 116564418, 664634151, 587878792, 42168675, 5988024, 5952381, 242603552, 335294120, 795321643, 98837210, 791907520, 626436786, 325714288, 51136364, 683615824, 207865170, 435754193, 205555557, 933701664, 82417583, 562841534, 92391305, 524324328, 521505380, 577540111, 601063834, 338624341, 615789478, 439790579, 380208336, 694300523, 634020623, 343589746, 862244904, 969543154, 823232329, 507537692, 285000002, 228855723, 470297033, 108374385, 946078438, 131707318, 286407769, 526570052, 197115386, 832535891, 604761909, 90047394, 514150947, 32863850, 612149537, 79069768, 671296301, 875576043, 4587156, 470319638, 440909094, 950226251, 436936940, 125560539, 754464291, 364444447, 446902658, 35242291, 846491234, 711790398, 73913044, 277056279, 969827593, 90128756, 619658124, 880851070, 512711868, 67510549, 239495800, 280334730, 904166673, 406639007, 219008266, 707818935, 922131154, 89795919, 443089434, 165991904, 391129035, 28112450, 428000003, 912350604, 3968254, 339920951, 240157482, 556862749, 285156252, 70038911, 399224809, 517374521, 757692313, 417624524, 95419848, 836501907, 367424245, 611320759, 582706771, 138576780, 421641794, 743494429, 137037038, 450184505, 209558825, 388278391, 529197084, 752727278, 394927539, 252707583, 802158279, 681003589, 203571430, 718861215, 67375887, 650176683, 524647891, 77192983, 416083919, 808362375, 253472224, 961937723, 575862073, 756013751, 852739732, 522184304, 574829936, 210169493, 327702705, 215488217, 265100673, 441471575, 523333337, 770764125, 241721856, 646864691, 134868422, 137704919, 297385623, 749185673, 457792211, 857605184, 312903228, 787781356, 464743593, 492012783, 671974527, 403174606, 800632917, 652996850, 342767298, 614420067, 428125003, 741433027, 481366463, 597523224, 780864203, 406153849, 58282209, 3058104, 832317079, 343465048, 293939396, 631419944, 521084341, 624624629, 2994012, 737313438, 502976194, 41543027, 121301776, 631268441, 167647060, 284457480, 897660825, 206997086, 49418605, 715942034, 395953760, 985590785, 313218393, 521489975, 162857144, 413105416, 25568182, 175637395, 341807912, 19718310, 103932585, 826330538, 717877100, 713091927, 602777782, 113573408, 466850832, 812672182, 541208795, 882191787, 281420767, 376021801, 546195656, 295392956, 262162164, 436657685, 260752690, 16085791, 788770059, 618666671, 300531917, 212201593, 669312174, 195250661, 307894739, 160104988, 719895293, 172323761, 190104168, 966233773, 847150265, 932816544, 817010315, 951156819, 171794873, 102301791, 431122452, 63613232, 484771577, 840506335, 911616168, 760705295, 253768846, 55137845, 142500001, 855361602, 614427865, 779156333, 735148520, 424691361, 554187196, 238329240, 473039219, 188264060, 65853659, 352798056, 643203888, 578692498, 263285026, 16867470, 98557693, 534772186, 916267949, 844868741, 802380958, 966745850, 45023697, 44917258, 757075477, 134117648, 16431925, 526932088, 806074772, 610722615, 39534884, 761020887, 835648154, 614318711, 937788025, 50574713, 2293578, 354691078, 235159819, 642369025, 220454547, 716553293, 975113129, 88036118, 218468470, 83146068, 562780273, 176733782, 877232149, 285077953, 682222227, 605321512, 223451329, 161147904, 517621149, 432967036, 423245617, 172866522, 355895199, 198257082, 36956522, 321041217, 638528143, 820734347, 984913800, 208602152, 45064378, 775160605, 309829062, 240938168, 440425535, 447983018, 256355934, 763213536, 533755278, 646315794, 119747900, 228511532, 140167365, 206680586, 952083340, 355509358, 703319507, 654244311, 109504133, 653608252, 853909471, 607802879, 461065577, 38854806, 544897963, 641547866, 221544717, 632860045, 82995952, 529292933, 695564521, 156941651, 14056225, 266533068, 714000005};

ll dp[505][1005];
map<pair<ll, ll>, ll> choose;

ll fastchoose(ll n, ll k) {
    pair<ll, ll> key = make_pair(n, k);
    if(choose[key] == 0) {
        if(n == 0) {
            choose[key] = 2;
            return (choose[key] + MOD - 1) % MOD; 
        }

        ll w = 1;

        for(int i = 1; i <= k; i++) {
            w = (w * (n - (i-1))) % MOD;
            w = (w * inv[i]) % MOD;
        }

        choose[key] = (w+1);
    }

    return (choose[key] + MOD - 1) % MOD;
}

ll modpow(ll b, ll e) {
    if(e <= 0) return 1ll;
    else if(e&1) return (b*modpow(b, e-1))%MOD;
    else return modpow(b*b%MOD, e/2);
}

int main() {
    fastIO;
    
    int v; cin >> v;
    vector<pair<int, int>> boat(v); for(auto &i : boat) cin >> i.first >> i.second;
    set<int> thing;
    thing.emplace(0);

    for(auto &i : boat) {thing.emplace(i.first); thing.emplace(i.second+1);}
    
    vector<int> ranges;
    unordered_map<int, int> ranges_back;

    for(auto i : thing) ranges.push_back(i);

    ll n = ranges.size() - 1;

    for(int i = 0; i < n+1; i++) ranges_back[ranges[i]] = i;

    vector<vector<int>> valids(n, {0});
    for(int i = 0; i < v; i++) {
        for(int j = 0; j < n; j++) {
            if(boat[i].first <= ranges[j] && ranges[j] <= boat[i].second) valids[j].push_back(i+1);
        }
    }

    // for(auto i : valids) {
    //     for(auto j : i) cerr << j << ' '; cerr << '\n';
    // }

    for(int i = 0; i <= n; i++) dp[0][i] = 1;
    for(int i = 0; i <= v; i++) dp[i][0] = 1;

    for(int i = 1; i < n; i++) {
        ll rsz = ranges[i+1] - ranges[i];

        // cerr << i << ' ' << rsz << '\n';
        
        for(ll range = 1; range < valids[i].size(); range++) {
            // calculate ways
            ll w = range!=1?0:fastchoose(rsz, 1);

            for(int ec = 0; ec <= min(range-2, rsz-2); ec++) {
                w = (w + (fastchoose(range-2, ec)*fastchoose(rsz, 2+ec))%MOD) % MOD;
            }

            for(int x = 1; x + range - 1 < valids[i].size(); x++) {
                dp[valids[i][x+range-1]][i] = (dp[valids[i][x+range-1]][i] + (w * dp[valids[i][x]-1][i-1]) % MOD) % MOD;
            }
        }

        for(int j = 1; j <= v; j++) {
            // printf("bef pref %d %d = %lld\n", j, i, dp[j][i]);

            dp[j][i] = (dp[j][i] + dp[j][i-1]) % MOD;
            dp[j][i] = (dp[j][i] + dp[j-1][i]) % MOD;
            dp[j][i] = (dp[j][i] - dp[j-1][i-1] + MOD) % MOD;
        }
    }

    // cout << dp[v][n];

    ll ans = (dp[v][n-1] - 1 + MOD) % MOD;
    // for(int i = 0; i <= v; i++) for(int range = 0; range < n; range++) printf("%d %d = %lld\n", i, range, dp[i][range]);
    // for(int i = 1; i <= v; i++) for(int range = 0; range < n; range++) ans = (ans + dp[i][range]) % MOD;

    // cout << ans;
    assert(ans >= 0);
    cout << ans;

    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42