QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380417#5532. Kangaroonhuang685#0 0ms0kbC++202.0kb2024-04-07 03:26:122024-07-04 03:33:31

Judging History

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

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

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);
#else
    std::freopen("kangaroo.in", "r", stdin);
    std::freopen("kangaroo.out", "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: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

7 3 6

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%