QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#271166#605. Alternating permutationhos_lyricAC ✓11ms3800kbC++144.7kb2023-12-02 02:16:162023-12-02 02:16:36

Judging History

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

  • [2023-12-02 02:16:36]
  • 评测
  • 测评结果:AC
  • 用时:11ms
  • 内存:3800kb
  • [2023-12-02 02:16:16]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 1000000007;
using Mint = ModInt<MO>;


/*
  DP determining small/large and relative position
  0: small
  1: large
  010 -> 0
  11 -> impossible
  100... -> left end fixed
  ...001 -> right end fixed
*/

int N, A, B;

int main() {
  for (; ~scanf("%d%d%d", &N, &A, &B); ) {
    // [k]: k 0's
    vector<Mint> crt{1};
    for (int x = 1; x <= N; ++x) {
      const int len = crt.size();
      vector<Mint> nxt(len + 1, 0);
      if (x == A || x == B) {
        for (int k = 0; k < len; ++k) {
          // 0
          nxt[k + 1] += crt[k];
          // 1
          if (k) nxt[k] += crt[k];
        }
      } else {
        // # of fixed ends
        const int s = ((A < x) ? 1 : 0) + ((B < x) ? 1 : 0);
        for (int k = 0; k < len; ++k) {
          // 0
          nxt[k + 1] += crt[k] * (k + 1 - s);
          // 1
          if (k) nxt[k - 1] += crt[k] * (k - 1);
        }
      }
      crt.swap(nxt);
    }
    const Mint ans = crt[1];
    printf("%u\n", ans.x);
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 11ms
memory: 3708kb

input:

2000 249 662

output:

979748465

result:

ok 1 number(s): "979748465"

Test #2:

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

input:

40 3 36

output:

636639342

result:

ok 1 number(s): "636639342"

Test #3:

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

input:

1080 615 886

output:

725146189

result:

ok 1 number(s): "725146189"

Test #4:

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

input:

2000 1505 232

output:

685039198

result:

ok 1 number(s): "685039198"

Test #5:

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

input:

2000 1727 623

output:

826160131

result:

ok 1 number(s): "826160131"

Test #6:

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

input:

2000 226 391

output:

540336141

result:

ok 1 number(s): "540336141"

Test #7:

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

input:

2000 703 1774

output:

376190159

result:

ok 1 number(s): "376190159"

Test #8:

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

input:

2000 1152 1096

output:

279880243

result:

ok 1 number(s): "279880243"

Test #9:

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

input:

1978 1073 500

output:

507169561

result:

ok 1 number(s): "507169561"

Test #10:

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

input:

2000 1992 1525

output:

738562126

result:

ok 1 number(s): "738562126"

Test #11:

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

input:

332 180 96

output:

981869781

result:

ok 1 number(s): "981869781"

Test #12:

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

input:

2000 509 1085

output:

264447286

result:

ok 1 number(s): "264447286"

Test #13:

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

input:

2000 1278 212

output:

205650795

result:

ok 1 number(s): "205650795"

Test #14:

score: 0
Accepted
time: 7ms
memory: 3776kb

input:

2000 1990 211

output:

968979327

result:

ok 1 number(s): "968979327"

Test #15:

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

input:

2000 1149 1516

output:

33004582

result:

ok 1 number(s): "33004582"

Test #16:

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

input:

1864 410 744

output:

472245768

result:

ok 1 number(s): "472245768"

Test #17:

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

input:

13 1 11

output:

101042

result:

ok 1 number(s): "101042"

Test #18:

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

input:

1998 821 973

output:

290007279

result:

ok 1 number(s): "290007279"

Test #19:

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

input:

2000 23 576

output:

932650726

result:

ok 1 number(s): "932650726"

Test #20:

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

input:

1078 504 314

output:

816976522

result:

ok 1 number(s): "816976522"

Test #21:

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

input:

1874 77 1372

output:

236095030

result:

ok 1 number(s): "236095030"

Test #22:

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

input:

2000 1640 910

output:

186485724

result:

ok 1 number(s): "186485724"

Test #23:

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

input:

883 468 652

output:

90531697

result:

ok 1 number(s): "90531697"

Test #24:

score: 0
Accepted
time: 7ms
memory: 3776kb

input:

2000 344 108

output:

473946379

result:

ok 1 number(s): "473946379"

Test #25:

score: 0
Accepted
time: 4ms
memory: 3732kb

input:

1177 728 957

output:

269338492

result:

ok 1 number(s): "269338492"

Test #26:

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

input:

642 351 495

output:

561170740

result:

ok 1 number(s): "561170740"

Test #27:

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

input:

2000 413 817

output:

897052865

result:

ok 1 number(s): "897052865"

Test #28:

score: 0
Accepted
time: 8ms
memory: 3656kb

input:

1767 69 638

output:

135415850

result:

ok 1 number(s): "135415850"

Test #29:

score: 0
Accepted
time: 7ms
memory: 3704kb

input:

2000 184 591

output:

232066123

result:

ok 1 number(s): "232066123"

Test #30:

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

input:

2000 256 348

output:

169245242

result:

ok 1 number(s): "169245242"

Test #31:

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

input:

1383 1029 240

output:

485589486

result:

ok 1 number(s): "485589486"

Test #32:

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

input:

620 15 70

output:

717885415

result:

ok 1 number(s): "717885415"

Test #33:

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

input:

2000 492 26

output:

981676302

result:

ok 1 number(s): "981676302"

Test #34:

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

input:

2000 1233 1252

output:

301114779

result:

ok 1 number(s): "301114779"

Test #35:

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

input:

353 204 113

output:

888055126

result:

ok 1 number(s): "888055126"

Test #36:

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

input:

2000 1030 311

output:

668443332

result:

ok 1 number(s): "668443332"

Test #37:

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

input:

2000 1038 1399

output:

961335740

result:

ok 1 number(s): "961335740"

Test #38:

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

input:

2000 1823 768

output:

927489489

result:

ok 1 number(s): "927489489"

Test #39:

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

input:

2000 753 858

output:

840245065

result:

ok 1 number(s): "840245065"

Test #40:

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

input:

2000 1996 113

output:

320982302

result:

ok 1 number(s): "320982302"

Test #41:

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

input:

1371 95 520

output:

261577724

result:

ok 1 number(s): "261577724"

Test #42:

score: 0
Accepted
time: 5ms
memory: 3728kb

input:

1317 885 324

output:

923532564

result:

ok 1 number(s): "923532564"

Test #43:

score: 0
Accepted
time: 7ms
memory: 3708kb

input:

2000 1156 1043

output:

47705941

result:

ok 1 number(s): "47705941"

Test #44:

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

input:

238 111 146

output:

611855732

result:

ok 1 number(s): "611855732"

Test #45:

score: 0
Accepted
time: 3ms
memory: 3704kb

input:

1486 281 79

output:

473052686

result:

ok 1 number(s): "473052686"

Test #46:

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

input:

2000 1711 1007

output:

931862496

result:

ok 1 number(s): "931862496"

Test #47:

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

input:

1871 1044 803

output:

479361145

result:

ok 1 number(s): "479361145"

Test #48:

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

input:

2000 1196 825

output:

550086503

result:

ok 1 number(s): "550086503"

Test #49:

score: 0
Accepted
time: 3ms
memory: 3700kb

input:

1526 968 659

output:

360125642

result:

ok 1 number(s): "360125642"

Test #50:

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

input:

2000 1640 616

output:

803535642

result:

ok 1 number(s): "803535642"