QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380418#5532. Kangaroonhuang685#51 29ms68304kbC++201.9kb2024-04-07 03:26:362024-07-04 03:33:31

Judging History

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

  • [2024-07-04 03:33:31]
  • 评测
  • 测评结果:51
  • 用时:29ms
  • 内存:68304kb
  • [2024-04-07 03:26:36]
  • 提交

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})));
    dp[1][1][1][0] = dp[1][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) {
                dp[i][st][fi][0] = psum(fi, i - 1, 1, dp[i - 1][st - 1]);
                dp[i][st][fi][1] = psum(1, fi - 1, 0, dp[i - 1][st - 1]);
            }
            for (int fi = st + 1; fi <= i; ++fi) {
                dp[i][st][fi][0] = psum(fi, i - 1, 1 , dp[i - 1][st]);
                dp[i][st][fi][1] = psum(1, fi - 1, 0, dp[i - 1][st]);
            }
            if (i < n) {
                for (int fi = 1; fi <= i; ++fi) {
                    for (int p : {0, 1}) {
                        dp[i][st][fi][p] += dp[i][st][fi - 1][p];
                    }
                }
            }
        }
    }
    std::cout << (dp[n][cs][cf][0] + dp[n][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: 3788kb

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: 1ms
memory: 3996kb

input:

39 36 32

output:

964903316

result:

ok 1 number(s): "964903316"

Test #3:

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

input:

26 1 26

output:

955348527

result:

ok 1 number(s): "955348527"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3716kb

input:

40 11 33

output:

695661890

result:

ok 1 number(s): "695661890"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

39 39 38

output:

717149364

result:

ok 1 number(s): "717149364"

Test #6:

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

input:

40 10 25

output:

912929610

result:

ok 1 number(s): "912929610"

Test #7:

score: 0
Accepted
time: 1ms
memory: 4016kb

input:

37 25 23

output:

250748685

result:

ok 1 number(s): "250748685"

Test #8:

score: 0
Accepted
time: 1ms
memory: 4068kb

input:

39 2 38

output:

624060592

result:

ok 1 number(s): "624060592"

Test #9:

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

input:

40 18 22

output:

739993796

result:

ok 1 number(s): "739993796"

Test #10:

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

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: 18ms
memory: 67704kb

input:

199 100 70

output:

914653136

result:

ok 1 number(s): "914653136"

Test #12:

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

input:

187 3 40

output:

928785584

result:

ok 1 number(s): "928785584"

Test #13:

score: 0
Accepted
time: 16ms
memory: 67660kb

input:

199 198 197

output:

38412688

result:

ok 1 number(s): "38412688"

Test #14:

score: 0
Accepted
time: 16ms
memory: 68256kb

input:

200 40 140

output:

367088143

result:

ok 1 number(s): "367088143"

Test #15:

score: 0
Accepted
time: 29ms
memory: 67572kb

input:

199 111 3

output:

870834793

result:

ok 1 number(s): "870834793"

Test #16:

score: 0
Accepted
time: 24ms
memory: 68304kb

input:

200 133 73

output:

343127012

result:

ok 1 number(s): "343127012"

Test #17:

score: 0
Accepted
time: 22ms
memory: 49236kb

input:

178 15 163

output:

160852284

result:

ok 1 number(s): "160852284"

Test #18:

score: 0
Accepted
time: 23ms
memory: 65692kb

input:

197 43 79

output:

332057544

result:

ok 1 number(s): "332057544"

Test #19:

score: 0
Accepted
time: 24ms
memory: 68244kb

input:

200 33 79

output:

742545318

result:

ok 1 number(s): "742545318"

Subtask #4:

score: 0
Memory Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #20:

score: 0
Memory Limit Exceeded

input:

658 169 438

output:

206087110

result: