QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#851767#8702. 狼人杀Xiaohuba100 ✓3484ms104660kbC++235.2kb2025-01-10 23:43:482025-01-10 23:43:50

Judging History

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

  • [2025-01-10 23:43:50]
  • 评测
  • 测评结果:100
  • 用时:3484ms
  • 内存:104660kb
  • [2025-01-10 23:43:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

// #define LOCK_GETCHAR
// #define USE_INT_128

#if __cplusplus < 201400
#warning "Please use c++14 or higher."
#define CONSTEXPR_FUNC
#define ENABLE_IF_INT
#else
#define CONSTEXPR_FUNC constexpr
#define ENABLE_IF_INT , enable_if_t<_is_integer<T>, int> = 0
template <class T> constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <> constexpr bool _is_integer<bool> = false;
template <> constexpr bool _is_integer<char> = false;
#ifdef USE_INT_128
template <> constexpr bool _is_integer<__int128> = true;
template <> constexpr bool _is_integer<__uint128_t> = true;
#endif
#endif

#if !defined(_WIN32) && !defined(__CYGWIN__) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif

#define il inline
#define mkp make_pair
#define fi first
#define se second
#define ssz(x) (signed((x).size()))
#define _loop_i_t(j, k) make_signed_t<decltype((j) - (k))>
#define For(i, j, k) for (_loop_i_t(j, k) i = (j); i <= (k); ++i) // NOLINT
#define ForDown(i, j, k)                                                       \
  for (_loop_i_t(j, k) i = (j); i >= decltype(i)(k); --i) // NOLINT
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename)                                                       \
  freopen(filename ".in", "r", stdin);                                         \
  freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif

// clang-format off
CONSTEXPR_FUNC il ll qpow(ll x, ull y, ll mod){ ll ans = 1; x %= mod; while (y) { if (y & 1) (ans *= x) %= mod; (x *= x) %= mod; y >>= 1; } return ans; }
template<typename T> CONSTEXPR_FUNC il void cmin(T & x, const T &y){ x = min(x, y); }
template<typename T> CONSTEXPR_FUNC il void cmax(T & x, const T &y){ x = max(x, y); }
template<typename T ENABLE_IF_INT> il void read(T &x){ x = 0; int f = 1; int c = getchar(); while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); } while (isdigit(c)) { x = x * 10 + (c - '0'); c = getchar(); } x *= f; }
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x), read(y...); }
// clang-format on

// File head end

namespace {
constexpr ll MAXN = 152, MAXM = MAXN * MAXN / 2, mod = 1e9 + 7;
int n, m, tot;
ll inv[MAXM], f[MAXN][MAXM][2], g[MAXN][MAXM][2], f2[MAXM][MAXN][2],
    g2[MAXM][MAXN][2], ans[MAXM], coef[MAXM];
ll pw[MAXM][MAXN], tmp[MAXM];
il int calc(int x) { return x * (x + 1) / 2; }
void lagrange() {
  vector<ll> F = {1}, tmp;
  For(i, 0, tot) {
    tmp.resize(i + 2), copy(F.begin(), F.end(), tmp.begin() + 1), tmp[0] = 0;
    For(j, 0, i)(tmp[j] += F[j] * (mod - i)) %= mod;
    F.swap(tmp);
  }
  For(i, 0, tot) {
    ll mul = ans[i];
    For(j, 0, i - 1)(mul *= inv[i - j]) %= mod;
    For(j, i + 1, tot)(mul *= mod - inv[j - i]) %= mod;
    static vector<ll> G(ssz(F));
    copy(F.begin(), F.end(), G.begin());
    ForDown(j, tot + 1, 1) {
      (coef[j - 1] += G[j] * mul) %= mod;
      (G[j - 1] += G[j] * i) %= mod, G[j] = 0;
    }
    assert(!G[0]);
  }
}
void Main() {
  read(n, m);
  inv[1] = 1, tot = n * (n + 1) / 2;
  For(i, 0, tot) { For(j, 0, n) pw[i][j] = qpow(i, calc(j), mod); }
  For(i, 2, tot) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
  ll sum = 0;
  For(i, 0, tot) f[m][i][0] = 1;
  ForDown(i, m - 1, 1) {
    For(j, i + 1, m) For(k, 0, tot) {
      int o = pw[k][j - i - 1];
      (f[i][k][0] += mod - f[j][k][0] * o % mod) %= mod;
      (f[i][k][1] += mod - f[j][k][1] * o % mod) %= mod;
      (f[i][k][1] += mod - f[j][k][0] * (j - i - 1) % mod * o % mod) %= mod;
    }
  }

  For(i, 0, tot) g[m][i][0] = 1;
  For(i, m + 1, n) {
    For(j, m, i - 1) For(k, 0, tot) {
      int o = pw[k][i - j - 1];
      (g[i][k][0] += mod - g[j][k][0] * o % mod) %= mod;
      (g[i][k][1] += mod - g[j][k][1] * o % mod) %= mod;
      (g[i][k][1] += mod - g[j][k][0] * (i - j - 1) % mod * o % mod) %= mod;
    }
  }

  For(i, 1, m) For(k, 0, tot) {
    ll u = f[i][k][0], v = f[i][k][1], o = pw[k][i - 1];
    f[i][k][0] = u * o % mod;
    f[i][k][1] = (u * (i - 1) + v) % mod * o % mod;
  }
  For(i, m, n) For(k, 0, tot) {
    ll u = g[i][k][0], v = g[i][k][1], o = pw[k][n - i];
    g[i][k][0] = u * o % mod;
    g[i][k][1] = (u * (n - i) + v) % mod * o % mod;
  }

  cerr << "OK1 " << 1. * clock() / CLOCKS_PER_SEC << '\n';

  For(i, 1, m) For(j, 0, tot) For(k, 0, 1) f2[j][i][k] = f[i][j][k];
  For(i, m, n) For(j, 0, tot) For(k, 0, 1) g2[j][i][k] = g[i][j][k];

  For(k, 0, tot) {
    tmp[0] = 1;
    For(i, 1, tot) tmp[i] = tmp[i - 1] * k % mod;
    For(i, 1, m) For(j, m, n) if (i != m || j != m) {
      ll mul = tmp[i * (n - j + 1)];
      For(o, 0, 1)(ans[k] += f2[k][i][o] * g2[k][j][o ^ 1] % mod * mul) %= mod;
    }
  }

  cerr << "OK2 " << 1. * clock() / CLOCKS_PER_SEC << '\n';

  lagrange();
  For(i, 0, tot)(sum += mod - coef[i] * inv[tot - i] % mod) %= mod;
  cout << sum * tot % mod * inv[n - 1] % mod << '\n';
}
} // namespace

signed main() { return Main(), 0; }

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 23
Accepted

Test #1:

score: 23
Accepted
time: 2ms
memory: 12292kb

input:

12 2

output:

183756997

result:

ok single line: '183756997'

Test #2:

score: 23
Accepted
time: 2ms
memory: 12420kb

input:

17 6

output:

97571903

result:

ok single line: '97571903'

Test #3:

score: 23
Accepted
time: 2ms
memory: 12164kb

input:

13 3

output:

209826617

result:

ok single line: '209826617'

Test #4:

score: 23
Accepted
time: 0ms
memory: 12480kb

input:

13 8

output:

176038768

result:

ok single line: '176038768'

Test #5:

score: 23
Accepted
time: 0ms
memory: 16272kb

input:

18 4

output:

288404061

result:

ok single line: '288404061'

Test #6:

score: 23
Accepted
time: 0ms
memory: 14244kb

input:

10 10

output:

219657163

result:

ok single line: '219657163'

Test #7:

score: 23
Accepted
time: 2ms
memory: 12424kb

input:

19 15

output:

590577825

result:

ok single line: '590577825'

Test #8:

score: 23
Accepted
time: 1ms
memory: 14484kb

input:

11 6

output:

488143489

result:

ok single line: '488143489'

Test #9:

score: 23
Accepted
time: 1ms
memory: 12252kb

input:

10 5

output:

470594541

result:

ok single line: '470594541'

Test #10:

score: 23
Accepted
time: 2ms
memory: 14384kb

input:

20 5

output:

582458555

result:

ok single line: '582458555'

Test #11:

score: 23
Accepted
time: 0ms
memory: 14584kb

input:

20 12

output:

648081410

result:

ok single line: '648081410'

Test #12:

score: 23
Accepted
time: 2ms
memory: 14468kb

input:

20 4

output:

335777285

result:

ok single line: '335777285'

Test #13:

score: 23
Accepted
time: 0ms
memory: 12608kb

input:

20 15

output:

389216500

result:

ok single line: '389216500'

Test #14:

score: 23
Accepted
time: 3ms
memory: 14588kb

input:

20 16

output:

582458555

result:

ok single line: '582458555'

Test #15:

score: 23
Accepted
time: 3ms
memory: 14520kb

input:

20 19

output:

589126150

result:

ok single line: '589126150'

Test #16:

score: 23
Accepted
time: 0ms
memory: 12472kb

input:

20 6

output:

389216500

result:

ok single line: '389216500'

Subtask #2:

score: 34
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 34
Accepted
time: 40ms
memory: 20468kb

input:

49 14

output:

486918542

result:

ok single line: '486918542'

Test #18:

score: 34
Accepted
time: 0ms
memory: 15104kb

input:

28 13

output:

642223597

result:

ok single line: '642223597'

Test #19:

score: 34
Accepted
time: 8ms
memory: 16648kb

input:

35 23

output:

842346505

result:

ok single line: '842346505'

Test #20:

score: 34
Accepted
time: 34ms
memory: 21784kb

input:

47 11

output:

583647040

result:

ok single line: '583647040'

Test #21:

score: 34
Accepted
time: 7ms
memory: 15380kb

input:

34 30

output:

990970048

result:

ok single line: '990970048'

Test #22:

score: 34
Accepted
time: 8ms
memory: 19016kb

input:

30 7

output:

393675971

result:

ok single line: '393675971'

Test #23:

score: 34
Accepted
time: 25ms
memory: 18032kb

input:

43 5

output:

737421246

result:

ok single line: '737421246'

Test #24:

score: 34
Accepted
time: 4ms
memory: 16688kb

input:

30 21

output:

254760745

result:

ok single line: '254760745'

Test #25:

score: 34
Accepted
time: 3ms
memory: 16276kb

input:

27 22

output:

266692865

result:

ok single line: '266692865'

Test #26:

score: 34
Accepted
time: 11ms
memory: 17804kb

input:

40 12

output:

133652311

result:

ok single line: '133652311'

Test #27:

score: 34
Accepted
time: 0ms
memory: 14832kb

input:

29 4

output:

873892090

result:

ok single line: '873892090'

Test #28:

score: 34
Accepted
time: 39ms
memory: 20880kb

input:

50 46

output:

267950067

result:

ok single line: '267950067'

Test #29:

score: 34
Accepted
time: 39ms
memory: 20924kb

input:

50 11

output:

423642322

result:

ok single line: '423642322'

Test #30:

score: 34
Accepted
time: 43ms
memory: 23988kb

input:

50 43

output:

625476642

result:

ok single line: '625476642'

Test #31:

score: 34
Accepted
time: 35ms
memory: 20752kb

input:

50 36

output:

767166129

result:

ok single line: '767166129'

Test #32:

score: 34
Accepted
time: 42ms
memory: 21596kb

input:

50 14

output:

357467965

result:

ok single line: '357467965'

Test #33:

score: 34
Accepted
time: 35ms
memory: 22100kb

input:

50 30

output:

219673347

result:

ok single line: '219673347'

Test #34:

score: 34
Accepted
time: 42ms
memory: 21452kb

input:

50 44

output:

392786132

result:

ok single line: '392786132'

Test #35:

score: 34
Accepted
time: 31ms
memory: 22104kb

input:

50 10

output:

848251616

result:

ok single line: '848251616'

Subtask #3:

score: 43
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #36:

score: 43
Accepted
time: 197ms
memory: 34128kb

input:

75 47

output:

668751416

result:

ok single line: '668751416'

Test #37:

score: 43
Accepted
time: 193ms
memory: 34616kb

input:

75 41

output:

310834114

result:

ok single line: '310834114'

Test #38:

score: 43
Accepted
time: 1984ms
memory: 83600kb

input:

133 124

output:

57167600

result:

ok single line: '57167600'

Test #39:

score: 43
Accepted
time: 1693ms
memory: 80416kb

input:

129 74

output:

751074385

result:

ok single line: '751074385'

Test #40:

score: 43
Accepted
time: 2107ms
memory: 85528kb

input:

135 133

output:

759430862

result:

ok single line: '759430862'

Test #41:

score: 43
Accepted
time: 204ms
memory: 35084kb

input:

75 19

output:

967921272

result:

ok single line: '967921272'

Test #42:

score: 43
Accepted
time: 1485ms
memory: 73112kb

input:

124 9

output:

641081661

result:

ok single line: '641081661'

Test #43:

score: 43
Accepted
time: 212ms
memory: 31764kb

input:

76 66

output:

465902083

result:

ok single line: '465902083'

Test #44:

score: 43
Accepted
time: 2646ms
memory: 95908kb

input:

142 13

output:

12401929

result:

ok single line: '12401929'

Test #45:

score: 43
Accepted
time: 3445ms
memory: 102420kb

input:

150 5

output:

388058135

result:

ok single line: '388058135'

Test #46:

score: 43
Accepted
time: 885ms
memory: 58104kb

input:

109 97

output:

381109644

result:

ok single line: '381109644'

Test #47:

score: 43
Accepted
time: 3352ms
memory: 103620kb

input:

150 133

output:

174431234

result:

ok single line: '174431234'

Test #48:

score: 43
Accepted
time: 3414ms
memory: 102360kb

input:

150 147

output:

198921722

result:

ok single line: '198921722'

Test #49:

score: 43
Accepted
time: 3388ms
memory: 102912kb

input:

150 142

output:

631473185

result:

ok single line: '631473185'

Test #50:

score: 43
Accepted
time: 3389ms
memory: 104448kb

input:

150 136

output:

743180069

result:

ok single line: '743180069'

Test #51:

score: 43
Accepted
time: 3419ms
memory: 104224kb

input:

150 138

output:

621574340

result:

ok single line: '621574340'

Test #52:

score: 43
Accepted
time: 3290ms
memory: 104660kb

input:

150 119

output:

872660153

result:

ok single line: '872660153'

Test #53:

score: 43
Accepted
time: 3390ms
memory: 102492kb

input:

150 144

output:

939939060

result:

ok single line: '939939060'

Test #54:

score: 43
Accepted
time: 3484ms
memory: 100992kb

input:

150 1

output:

166208360

result:

ok single line: '166208360'

Test #55:

score: 43
Accepted
time: 3203ms
memory: 103312kb

input:

150 75

output:

353929212

result:

ok single line: '353929212'