QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382059#5532. Kangaroonhuang685100 ✓14ms18996kbC++204.3kb2024-04-08 01:28:212024-04-08 01:28:23

Judging History

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

  • [2024-04-08 01:28:23]
  • 评测
  • 测评结果:100
  • 用时:14ms
  • 内存:18996kb
  • [2024-04-08 01:28:21]
  • 提交

answer

/**
 * @file qoj5532-2.cpp
 * @author n685
 * @brief
 * @date 2024-04-06
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

template <class T> constexpr std::pair<T, T> exEucl(T a, T b) {
  if (a < b) {
    // auto [x, y] = exEucl(b, a);
    T x, y;
    std::tie(x, y) = exEucl(b, a);
    return {y, x};
  }
  if (b == 0) {
    assert(a == 1);
    return {1, 0};
  }
  // auto [x, y] = exEucl(b, a % b);
  T x, y;
  std::tie(x, y) = exEucl(b, a % b);
  return {y, x - (a / b) * y};
}
template <
    class T, class U,
    typename std::enable_if<std::is_integral<U>::value, bool>::type = true>
constexpr T binpow(T a, U b) {
  // 0^0 = 1
  T res = 1;
  while (b > 0) {
    if (b % 2 == 1) {
      res *= a;
    }
    a *= a;
    b /= 2;
  }
  return res;
}

template <class Md, class V = int64_t> struct Mod {
  using T = typename std::decay<decltype(Md::value)>::type;
  T val = 0;

  template <class U> static constexpr T normalize(U val) {
    if (val <= -Md::value || Md::value <= val) {
      val %= Md::value;
    }
    if (val < 0) {
      val += Md::value;
    }
    return static_cast<T>(val);
  }

  constexpr Mod() : val(0) {}
  template <class U, typename std::enable_if<std::is_integral<U>::value,
                                             bool>::type = true>
  constexpr Mod(U _val) {
    val = normalize(_val);
  }

  // addition
  constexpr Mod &operator+=(Mod b) {
    val += b.val;
    if (val >= Md::value) {
      val -= Md::value;
    }
    return *this;
  }
  friend constexpr Mod operator+(Mod a, Mod b) { return (a += b); }
  constexpr Mod &operator++() { return (*this += 1); }
  constexpr Mod operator++(int) {
    Mod res = *this;
    ++(*this);
    return res;
  }

  // subtraction
  constexpr Mod &operator-=(Mod b) {
    val -= b.val;
    if (val < 0) {
      val += Md::value;
    }
    return *this;
  }
  friend constexpr Mod operator-(Mod a, Mod b) { return (a -= b); }
  constexpr Mod &operator--() { return (*this -= 1); }
  constexpr Mod operator--(int) {
    Mod res = *this;
    --(*this);
    return res;
  }

  // multiplication
  constexpr Mod &operator*=(Mod b) {
    val = static_cast<T>(static_cast<V>(val) * b.val % Md::value);
    return *this;
  }
  friend constexpr Mod operator*(Mod a, Mod b) { return (a *= b); }

  template <class U> constexpr Mod binpow(U b) const {
    return ::binpow(*this, b);
  }
  constexpr Mod inv() const {
    return Mod(exEucl(static_cast<V>(val), static_cast<V>(Md::value)).first);
    // return binpow(Md::value - 2);
  }

  // comparison
  constexpr bool operator==(Mod b) const { return (val == b.val); }
  // constexpr auto operator<=>(const Mod &b) const = default;
  constexpr bool operator!=(Mod b) const { return (val != b.val); }
  constexpr bool operator<(Mod b) const { return (val < b.val); }
  constexpr bool operator>(Mod b) const { return (val > b.val); }
  constexpr bool operator<=(Mod b) const { return (val <= b.val); }
  constexpr bool operator>=(Mod b) const { return (val >= b.val); }

  // io
  friend std::istream &operator>>(std::istream &in, Mod &a) {
    V v;
    in >> v;
    a = Mod(v);
    return in;
  }
  friend std::ostream &operator<<(std::ostream &out, const Mod &a) {
    out << a.val;
    return out;
  }

  // conversion
  explicit constexpr operator T() const { return val; }
  constexpr const T &operator()() const { return val; }
  constexpr Mod operator-() const { return Mod(-val); }
};

constexpr int MOD = (int)1e9 + 7;
using Mint = Mod<std::integral_constant<std::decay<decltype(MOD)>::type, MOD>>;

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

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

  std::vector dp(n + 1, std::vector<Mint>(n + 1));
  dp[1][1] = 1;
  for (int i : std::views::iota(2, n + 1)) {
    for (int j : std::views::iota(1, i + 1)) {
      if (i == cs || i == cf) {
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
      } else {
        if (j < i - 1) {
          dp[i][j] += j * dp[i - 1][j + 1];
        }
        dp[i][j] += (j - (i > cs) - (i > cf)) * dp[i - 1][j - 1];
      }
    }
  }

  std::cout << dp[n][1] << '\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: 3456kb

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: 3468kb

input:

39 36 32

output:

964903316

result:

ok 1 number(s): "964903316"

Test #3:

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

input:

26 1 26

output:

955348527

result:

ok 1 number(s): "955348527"

Test #4:

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

input:

40 11 33

output:

695661890

result:

ok 1 number(s): "695661890"

Test #5:

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

input:

39 39 38

output:

717149364

result:

ok 1 number(s): "717149364"

Test #6:

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

input:

40 10 25

output:

912929610

result:

ok 1 number(s): "912929610"

Test #7:

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

input:

37 25 23

output:

250748685

result:

ok 1 number(s): "250748685"

Test #8:

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

input:

39 2 38

output:

624060592

result:

ok 1 number(s): "624060592"

Test #9:

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

input:

40 18 22

output:

739993796

result:

ok 1 number(s): "739993796"

Test #10:

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

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: 0ms
memory: 3748kb

input:

199 100 70

output:

914653136

result:

ok 1 number(s): "914653136"

Test #12:

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

input:

187 3 40

output:

928785584

result:

ok 1 number(s): "928785584"

Test #13:

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

input:

199 198 197

output:

38412688

result:

ok 1 number(s): "38412688"

Test #14:

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

input:

200 40 140

output:

367088143

result:

ok 1 number(s): "367088143"

Test #15:

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

input:

199 111 3

output:

870834793

result:

ok 1 number(s): "870834793"

Test #16:

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

input:

200 133 73

output:

343127012

result:

ok 1 number(s): "343127012"

Test #17:

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

input:

178 15 163

output:

160852284

result:

ok 1 number(s): "160852284"

Test #18:

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

input:

197 43 79

output:

332057544

result:

ok 1 number(s): "332057544"

Test #19:

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

input:

200 33 79

output:

742545318

result:

ok 1 number(s): "742545318"

Subtask #4:

score: 49
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #20:

score: 49
Accepted
time: 2ms
memory: 4860kb

input:

658 169 438

output:

206087110

result:

ok 1 number(s): "206087110"

Test #21:

score: 0
Accepted
time: 2ms
memory: 5196kb

input:

700 207 509

output:

478311263

result:

ok 1 number(s): "478311263"

Test #22:

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

input:

755 139 507

output:

103783948

result:

ok 1 number(s): "103783948"

Test #23:

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

input:

2000 500 1500

output:

123410309

result:

ok 1 number(s): "123410309"

Test #24:

score: 0
Accepted
time: 10ms
memory: 18928kb

input:

2000 1000 1001

output:

956197482

result:

ok 1 number(s): "956197482"

Test #25:

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

input:

2000 666 1333

output:

993781645

result:

ok 1 number(s): "993781645"

Test #26:

score: 0
Accepted
time: 14ms
memory: 18620kb

input:

1991 198 677

output:

155058730

result:

ok 1 number(s): "155058730"

Test #27:

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

input:

1498 299 659

output:

665757882

result:

ok 1 number(s): "665757882"