QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380431#5532. Kangaroonhuang685#0 0ms3588kbC++201.9kb2024-04-07 03:50:082024-07-04 03:33:32

Judging History

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

  • [2024-07-04 03:33:32]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3588kb
  • [2024-04-07 03:50:08]
  • 提交

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::array<Mint, 2>{0, 0});
    std::vector pre = cur;
    pre[cs][0] = pre[cs][1] = 1;
    for (int i = 2; i <= n; ++i) {
        int l = cs - i + 1;
        int r = cs + i - 1;
        for (int fi = std::max(1, l); fi < cs; ++fi) {
            cur[fi][0] = psum(fi + 1, std::min(n, r - 1), 1, pre);
            cur[fi][1] = psum(std::max(2, l + 1), fi, 0, pre);
        }
        for (int fi = cs + 1; fi <= std::min(n, r); ++fi) {
            cur[fi][0] = psum(fi, std::min(n - 1, r - 1), 1, pre);
            cur[fi][1] = psum(std::max(1, l + 1), fi - 1, 0, pre);
        }
        if (i < n) {
            for (int j = 1; j <= n; ++j) {
                cur[j][0] += cur[j - 1][0];
                cur[j][1] += cur[j - 1][1];
            }
        }
        pre = cur;
        cur.assign(n + 1, std::array<Mint, 2>{0, 0});
    }
    std::cout << (pre[cf][0] + pre[cf][1]).val << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3588kb

input:

7 3 6

output:

124

result:

wrong answer 1st numbers differ - expected: '14', found: '124'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%