QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380420#5532. Kangaroonhuang685#51 875ms12036kbC++202.0kb2024-04-07 03:30:182024-07-04 03:33:32

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 03:33:32]
  • 评测
  • 测评结果:51
  • 用时:875ms
  • 内存:12036kb
  • [2024-04-07 03:30:18]
  • 提交

answer

#include <bits/stdc++.h>

const int MOD = (int)1e9 + 7;
struct Mint {
    int val;
    Mint(int v = 0) : val((v % MOD + MOD) % MOD) {}
    Mint &operator+=(Mint b) {
        val += b.val;
        if (val >= MOD) {
            val -= MOD;
        }
        return *this;
    }
    Mint &operator-=(Mint b) {
        val -= b.val;
        if (val < 0) {
            val += MOD;
        }
        return *this;
    }
};
Mint operator+(Mint a, Mint b) { return a += b; }
Mint operator-(Mint a, Mint b) { return a -= b; }

Mint psum(int l, int r, int p, std::vector<std::array<Mint, 2>> &v) {
    if (l > r) {
        return 0;
    }
    return v[r][p] - v[l - 1][p];
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

#ifdef LOCAL
    std::freopen("input.txt", "r", stdin);
    std::freopen("output.txt", "w", stdout);
#endif

    int n, cs, cf;
    std::cin >> n >> cs >> cf;

    // std::vector dp(n + 1, std::vector(n + 1, std::vector(n + 1, std::array<Mint, 2>{0, 0})));
    std::vector cur(n + 1, std::vector(n + 1, std::array<Mint, 2>{0, 0}));
    std::vector pre = cur;
    pre[1][1][0] = pre[1][1][1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int st = 1; st <= i; ++st) {
            for (int fi = 1; fi < st; ++fi) {
                cur[st][fi][0] = psum(fi, i - 1, 1, pre[st - 1]);
                cur[st][fi][1] = psum(1, fi - 1, 0, pre[st - 1]);
            }
            for (int fi = st + 1; fi <= i; ++fi) {
                cur[st][fi][0] = psum(fi, i - 1, 1 , pre[st]);
                cur[st][fi][1] = psum(1, fi - 1, 0, pre[st]);
            }
            if (i < n) {
                for (int fi = 1; fi <= i; ++fi) {
                    for (int p : {0, 1}) {
                        cur[st][fi][p] += cur[st][fi - 1][p];
                    }
                }
            }
        }
        pre = cur;
        cur.assign(n + 1, std::vector(n + 1, std::array<Mint, 2>{0, 0}));
    }
    std::cout << (pre[cs][cf][0] + pre[cs][cf][1]).val << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 0ms
memory: 3840kb

input:

7 3 6

output:

14

result:

ok 1 number(s): "14"

Subtask #2:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #2:

score: 30
Accepted
time: 0ms
memory: 3648kb

input:

39 36 32

output:

964903316

result:

ok 1 number(s): "964903316"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

26 1 26

output:

955348527

result:

ok 1 number(s): "955348527"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

40 11 33

output:

695661890

result:

ok 1 number(s): "695661890"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

39 39 38

output:

717149364

result:

ok 1 number(s): "717149364"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

40 10 25

output:

912929610

result:

ok 1 number(s): "912929610"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

37 25 23

output:

250748685

result:

ok 1 number(s): "250748685"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

39 2 38

output:

624060592

result:

ok 1 number(s): "624060592"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

40 18 22

output:

739993796

result:

ok 1 number(s): "739993796"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

40 11 35


output:

135213497

result:

ok 1 number(s): "135213497"

Subtask #3:

score: 15
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 15
Accepted
time: 10ms
memory: 3852kb

input:

199 100 70

output:

914653136

result:

ok 1 number(s): "914653136"

Test #12:

score: 0
Accepted
time: 11ms
memory: 3972kb

input:

187 3 40

output:

928785584

result:

ok 1 number(s): "928785584"

Test #13:

score: 0
Accepted
time: 13ms
memory: 3832kb

input:

199 198 197

output:

38412688

result:

ok 1 number(s): "38412688"

Test #14:

score: 0
Accepted
time: 13ms
memory: 3908kb

input:

200 40 140

output:

367088143

result:

ok 1 number(s): "367088143"

Test #15:

score: 0
Accepted
time: 13ms
memory: 3872kb

input:

199 111 3

output:

870834793

result:

ok 1 number(s): "870834793"

Test #16:

score: 0
Accepted
time: 13ms
memory: 3996kb

input:

200 133 73

output:

343127012

result:

ok 1 number(s): "343127012"

Test #17:

score: 0
Accepted
time: 9ms
memory: 3676kb

input:

178 15 163

output:

160852284

result:

ok 1 number(s): "160852284"

Test #18:

score: 0
Accepted
time: 12ms
memory: 3824kb

input:

197 43 79

output:

332057544

result:

ok 1 number(s): "332057544"

Test #19:

score: 0
Accepted
time: 13ms
memory: 3924kb

input:

200 33 79

output:

742545318

result:

ok 1 number(s): "742545318"

Subtask #4:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #20:

score: 49
Accepted
time: 596ms
memory: 10064kb

input:

658 169 438

output:

206087110

result:

ok 1 number(s): "206087110"

Test #21:

score: 0
Accepted
time: 710ms
memory: 10692kb

input:

700 207 509

output:

478311263

result:

ok 1 number(s): "478311263"

Test #22:

score: 0
Accepted
time: 875ms
memory: 12036kb

input:

755 139 507

output:

103783948

result:

ok 1 number(s): "103783948"

Test #23:

score: -49
Time Limit Exceeded

input:

2000 500 1500

output:


result: