QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#889489#1084. Beautiful Sequence UnravelingcaijianhongAC ✓329ms5760kbC++173.5kb2025-02-08 16:15:342025-02-08 16:16:09

Judging History

This is the latest submission verdict.

  • [2025-02-08 16:16:09]
  • Judged
  • Verdict: AC
  • Time: 329ms
  • Memory: 5760kb
  • [2025-02-08 16:15:34]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
template <class T>
using must_int = enable_if_t<is_integral<T>::value, int>;
template <int id>
struct modint {/*{{{*/
  static int mod;
  static unsigned umod;
  static void setmod(int p) { mod = umod = p; }
  unsigned v;
  modint() : v(0) {}
  template <class T, must_int<T> = 0>
  modint(T x) {
    x %= mod;
    v = x < 0 ? x + mod : x;
  }
  modint operator+() const { return *this; }
  modint operator-() const { return modint() - *this; }
  friend int raw(const modint &self) { return self.v; }
  friend ostream& operator<<(ostream& os, const modint &self) { 
    return os << raw(self); 
  }
  modint &operator+=(const modint &rhs) {
    v += rhs.v;
    if (v >= umod) v -= umod;
    return *this;
  }
  modint &operator-=(const modint &rhs) {
    v -= rhs.v;
    if (v >= umod) v += umod;
    return *this;
  }
  modint &operator*=(const modint &rhs) {
    v = 1ull * v * rhs.v % umod;
    return *this;
  }
  modint &operator/=(const modint &rhs) {
    assert(rhs.v);
    return *this *= qpow(rhs, mod - 2);
  }
  template <class T, must_int<T> = 0>
  friend modint qpow(modint a, T b) {
    modint r = 1;
    for (; b; b >>= 1, a *= a)
      if (b & 1) r *= a;
    return r;
  }
  friend modint operator+(modint lhs, const modint &rhs) { return lhs += rhs; }
  friend modint operator-(modint lhs, const modint &rhs) { return lhs -= rhs; }
  friend modint operator*(modint lhs, const modint &rhs) { return lhs *= rhs; }
  friend modint operator/(modint lhs, const modint &rhs) { return lhs /= rhs; }
  bool operator==(const modint &rhs) const { return v == rhs.v; }
  bool operator!=(const modint &rhs) const { return v != rhs.v; }
};/*}}}*/
template <int id>
unsigned modint<id>::umod;
template <int id>
int modint<id>::mod;
using mint = modint<-1>;
int n, m;
mint f[410][410], pw[410][410], binom[410][410], a[410], inv[410];
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  cin >> n >> m >> mint::mod;
  mint::setmod(mint::mod);
  for (int i = 0; i <= n; i++) {
    pw[i][0] = binom[i][0] = 1;
    for (int j = 1; j <= n; j++) pw[i][j] = pw[i][j - 1] * i;
    for (int j = 1; j <= i; j++) binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
  }
  inv[1] = 1;
  for (int i = 2; i <= n; i++) inv[i] = -mint::mod / i * inv[mint::mod % i];
  for (int j = 1; j <= n; j++) {
    for (int i = 1; i <= n; i++) {
      f[i][j] = pw[j][i];
    }
  }
  for (int j = 1; j <= n; j++) {
//    mint now1 = 0, now2 = 0;
      mint now1[410] = {}, now2[410] = {};
      for (int i = 1; i <= n; i++) {
        for (int t = 1; t <= j; t++) f[i][j] -= now1[t] - now2[t];
        for (int t = 1; t <= j; t++) {
          now1[t] = (now1[t] + f[i][j - t + 1] - f[i][j - t]) * t;
          now2[t] = (now2[t] + f[i][j - t + 1] - f[i][j - t]) * (t - 1);
        }
        // for (int k = 1; k < i; k++) {
        //   f[i][j] -= (pw[t][k] - pw[t - 1][k]) * (f[i - k][j - t + 1] - f[i - k][j - t]);
        // }
      }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) a[i] += binom[i][j] * ((i - j) & 1 ? -1 : +1) * f[n][j];
  }
  mint ans = 0;
  mint now = 1;
  for (int i = 1; i <= n; i++) {
    now *= m - i + 1;
    now *= inv[i];
    ans += now * a[i];
  }
  cout << ans << endl;
  return 0;
}


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5760kb

input:

2 2 1000000007

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3 4 1000000009

output:

36

result:

ok 1 number(s): "36"

Test #3:

score: 0
Accepted
time: 61ms
memory: 5760kb

input:

228 112263 998244353

output:

379700769

result:

ok 1 number(s): "379700769"

Test #4:

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

input:

1 1 998595277

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 2 998683811

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

3 1 998277223

output:

0

result:

ok 1 number(s): "0"

Test #7:

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

input:

4 1 998365733

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 328ms
memory: 5760kb

input:

400 100000000 998244353

output:

318973800

result:

ok 1 number(s): "318973800"

Test #9:

score: 0
Accepted
time: 327ms
memory: 5760kb

input:

400 1 1000000007

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

2 9 999603883

output:

72

result:

ok 1 number(s): "72"

Test #11:

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

input:

1 1 998784541

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

3 3 999209353

output:

12

result:

ok 1 number(s): "12"

Test #13:

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

input:

4 12 999787531

output:

16544

result:

ok 1 number(s): "16544"

Test #14:

score: 0
Accepted
time: 327ms
memory: 5760kb

input:

400 3 998785127

output:

505031599

result:

ok 1 number(s): "505031599"

Test #15:

score: 0
Accepted
time: 327ms
memory: 5632kb

input:

400 77 999400643

output:

877578741

result:

ok 1 number(s): "877578741"

Test #16:

score: 0
Accepted
time: 326ms
memory: 5760kb

input:

400 374 998458939

output:

202865317

result:

ok 1 number(s): "202865317"

Test #17:

score: 0
Accepted
time: 329ms
memory: 5632kb

input:

400 77435643 999245677

output:

833344996

result:

ok 1 number(s): "833344996"

Test #18:

score: 0
Accepted
time: 325ms
memory: 5760kb

input:

399 72119824 999010279

output:

188282648

result:

ok 1 number(s): "188282648"

Test #19:

score: 0
Accepted
time: 323ms
memory: 5632kb

input:

398 22521432 999827603

output:

986913334

result:

ok 1 number(s): "986913334"

Test #20:

score: 0
Accepted
time: 320ms
memory: 5632kb

input:

397 77955743 998803427

output:

32764673

result:

ok 1 number(s): "32764673"