QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#525726#8702. 狼人杀Fido_Puppy100 ✓2585ms4324kbC++234.8kb2024-08-20 21:10:192024-08-20 21:10:19

Judging History

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

  • [2024-08-20 21:10:19]
  • 评测
  • 测评结果:100
  • 用时:2585ms
  • 内存:4324kb
  • [2024-08-20 21:10:19]
  • 提交

answer

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
#define eb emplace_back
#define rz resize
#define MP make_pair
#define MT make_tuple
#define IT iterator
#define fi first
#define se second
#define For(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define Rep(i, a, b) for (int i = (int)(a); i >= (int)(b); --i)
#define CLR(a, v) memset(a, v, sizeof(a))
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define debug cerr << "ztxakking\n"
#define y0 ztxaknoi
#define y1 ztxakioi
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using vi = vector<int>;
template<typename T>
using V = vector<T>;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template<const int MOD>
struct Modular {
  int val;
  Modular() = default;
  Modular(int x) : val(x) {}
  friend Modular operator + (Modular x, Modular y) { int res = x.val + y.val; if (res >= MOD) res -= MOD; return res; }
  friend Modular operator - (Modular x, Modular y) { int res = x.val - y.val; if (res < 0) res += MOD; return res; }
  friend Modular operator * (Modular x, Modular y) { int res = 1ll * x.val * y.val % MOD; return res; }
  Modular &operator += (Modular x) { *this = *this + x; return *this; }
  Modular &operator -= (Modular x) { *this = *this - x; return *this; }
  Modular &operator *= (Modular x) { *this = *this * x; return *this; }
  Modular &operator ++ () { *this = *this + 1; return *this; }
  Modular &operator ++ (int) { *this = *this + 1; return *this; }
  Modular &operator -- () { *this = *this - 1; return *this; }
  Modular &operator -- (int) { *this = *this - 1; return *this; }
  Modular operator - () { int res = val; if (res) res = MOD - res; return res; }
  static Modular pow(Modular x, ll p) {
    Modular ans(1);
    for (; p; p /= 2, x *= x) {
      if (p & 1) ans *= x;
    }
    return ans;
  }
  static Modular inv(Modular x) { return pow(x, MOD - 2); }
  friend Modular operator / (Modular x, Modular y) { return x * inv(y); }
  Modular &operator /= (Modular x) { *this = *this / x; return *this; }
  friend bool operator == (Modular x, Modular y) { return x.val == y.val; }
  friend bool operator != (Modular x, Modular y) { return x.val != y.val; }
  friend istream &operator >> (istream &in, Modular &item) { in >> item.val; return in; }
  friend ostream &operator << (ostream &out, Modular item) { out << item.val; return out; }
};
using mint = Modular<1000000007>;
const int N = 157, M = 1.2e4 + 7;
int n, m, L;
mint pw[M], w[M], fac[M], ifac[M];
V<mint> operator + (V<mint> a, V<mint> b) {
  int n = a.size() - 1, m = b.size() - 1;
  V<mint> c(max(n, m) + 1, 0);
  For(i, 0, n) c[i] += a[i];
  For(i, 0, m) c[i] += b[i];
  return c;
}
V<mint> operator - (V<mint> a, V<mint> b) {
  int n = a.size() - 1, m = b.size() - 1;
  V<mint> c(max(n, m) + 1, 0);
  For(i, 0, n) c[i] += a[i];
  For(i, 0, m) c[i] -= b[i];
  return c;
}
V<mint> operator * (V<mint> a, mint t) {
  V<mint> b = a;
  for (auto &i : b) i *= t;
  return b;
}
V<mint> operator * (V<mint> a, V<mint> b) {
  int n = a.size() - 1, m = b.size() - 1;
  V<mint> c(n + m + 1, 0);
  For(i, 0, n) For(j, 0, m) c[i + j] += a[i] * b[j];
  return c;
}
V<mint> Inv(V<mint> a) {
  int n = a.size() - 1;
  V<mint> b(n + 1, 0);
  mint t = mint().inv(a[0]);
  b[0] = t;
  For(i, 1, n) {
    For(j, 1, i) b[i] -= a[j] * b[i - j];
    b[i] *= t;
  }
  return b;
}
pair<V<mint>, V<mint>> solve(int l, int r) {
  if (l == r) {
    mint t = w[l] * ifac[l] * ifac[L - l];
    if (L - l & 1) t = -t;
    V<mint> f(1, t), g(2, 1);
    g[0] = -mint(l);
    return {f, g};
  }
  int mid = (l + r) / 2;
  auto [fl, gl] = solve(l, mid);
  auto [fr, gr] = solve(mid + 1, r);
  return {fl * gr + fr * gl, gl * gr};
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m, L = n * (n + 1) / 2;
  if (n == 2) return cout << "0\n", 0;
  For(y, 0, L) {
    pw[0] = 1;
    For(i, 1, L) pw[i] = pw[i - 1] * y;
    V<mint> a(n + 1, 0), e(1, 1);
    For(i, 1, n) a[i] = -pw[i * (i - 1) / 2];
    V<mint> b = Inv(e - a), c = a * b * b;
    c.rz(n + 1);
    V<mint> f = b * (m - 1) - c, g = b * (n - m) - c;
    mint ans = 0;
    For(l, 0, m - 1) For(r, 0, n - m) if (l || r) {
      ans -= (f[l] * b[r] + g[r] * b[l]) * pw[(m - l) * (n - m - r + 1) + (m - l) * (m - l - 1) / 2 + (n - m - r + 1) * (n - m - r) / 2];
    }
    w[y] = ans;
  }
  fac[0] = 1;
  For(i, 1, L) fac[i] = fac[i - 1] * i;
  ifac[L] = 1 / fac[L];
  Rep(i, L, 1) ifac[i - 1] = ifac[i] * i;
  auto [f, g] = solve(0, L);
  mint ans = 0;
  For(i, 0, L - 1) ans += mint().inv(L - i) * f[i];
  ans *= L * mint().inv(n - 1);
  cout << ans << '\n';
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 23
Accepted

Test #1:

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

input:

12 2

output:

183756997

result:

ok single line: '183756997'

Test #2:

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

input:

17 6

output:

97571903

result:

ok single line: '97571903'

Test #3:

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

input:

13 3

output:

209826617

result:

ok single line: '209826617'

Test #4:

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

input:

13 8

output:

176038768

result:

ok single line: '176038768'

Test #5:

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

input:

18 4

output:

288404061

result:

ok single line: '288404061'

Test #6:

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

input:

10 10

output:

219657163

result:

ok single line: '219657163'

Test #7:

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

input:

19 15

output:

590577825

result:

ok single line: '590577825'

Test #8:

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

input:

11 6

output:

488143489

result:

ok single line: '488143489'

Test #9:

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

input:

10 5

output:

470594541

result:

ok single line: '470594541'

Test #10:

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

input:

20 5

output:

582458555

result:

ok single line: '582458555'

Test #11:

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

input:

20 12

output:

648081410

result:

ok single line: '648081410'

Test #12:

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

input:

20 4

output:

335777285

result:

ok single line: '335777285'

Test #13:

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

input:

20 15

output:

389216500

result:

ok single line: '389216500'

Test #14:

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

input:

20 16

output:

582458555

result:

ok single line: '582458555'

Test #15:

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

input:

20 19

output:

589126150

result:

ok single line: '589126150'

Test #16:

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

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: 32ms
memory: 3636kb

input:

49 14

output:

486918542

result:

ok single line: '486918542'

Test #18:

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

input:

28 13

output:

642223597

result:

ok single line: '642223597'

Test #19:

score: 34
Accepted
time: 9ms
memory: 3668kb

input:

35 23

output:

842346505

result:

ok single line: '842346505'

Test #20:

score: 34
Accepted
time: 26ms
memory: 3688kb

input:

47 11

output:

583647040

result:

ok single line: '583647040'

Test #21:

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

input:

34 30

output:

990970048

result:

ok single line: '990970048'

Test #22:

score: 34
Accepted
time: 5ms
memory: 3652kb

input:

30 7

output:

393675971

result:

ok single line: '393675971'

Test #23:

score: 34
Accepted
time: 15ms
memory: 3864kb

input:

43 5

output:

737421246

result:

ok single line: '737421246'

Test #24:

score: 34
Accepted
time: 5ms
memory: 3668kb

input:

30 21

output:

254760745

result:

ok single line: '254760745'

Test #25:

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

input:

27 22

output:

266692865

result:

ok single line: '266692865'

Test #26:

score: 34
Accepted
time: 15ms
memory: 3912kb

input:

40 12

output:

133652311

result:

ok single line: '133652311'

Test #27:

score: 34
Accepted
time: 2ms
memory: 3660kb

input:

29 4

output:

873892090

result:

ok single line: '873892090'

Test #28:

score: 34
Accepted
time: 28ms
memory: 3664kb

input:

50 46

output:

267950067

result:

ok single line: '267950067'

Test #29:

score: 34
Accepted
time: 33ms
memory: 3720kb

input:

50 11

output:

423642322

result:

ok single line: '423642322'

Test #30:

score: 34
Accepted
time: 33ms
memory: 3724kb

input:

50 43

output:

625476642

result:

ok single line: '625476642'

Test #31:

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

input:

50 36

output:

767166129

result:

ok single line: '767166129'

Test #32:

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

input:

50 14

output:

357467965

result:

ok single line: '357467965'

Test #33:

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

input:

50 30

output:

219673347

result:

ok single line: '219673347'

Test #34:

score: 34
Accepted
time: 33ms
memory: 3728kb

input:

50 44

output:

392786132

result:

ok single line: '392786132'

Test #35:

score: 34
Accepted
time: 33ms
memory: 3888kb

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: 167ms
memory: 3788kb

input:

75 47

output:

668751416

result:

ok single line: '668751416'

Test #37:

score: 43
Accepted
time: 168ms
memory: 3748kb

input:

75 41

output:

310834114

result:

ok single line: '310834114'

Test #38:

score: 43
Accepted
time: 1445ms
memory: 4120kb

input:

133 124

output:

57167600

result:

ok single line: '57167600'

Test #39:

score: 43
Accepted
time: 1406ms
memory: 3924kb

input:

129 74

output:

751074385

result:

ok single line: '751074385'

Test #40:

score: 43
Accepted
time: 1494ms
memory: 4064kb

input:

135 133

output:

759430862

result:

ok single line: '759430862'

Test #41:

score: 43
Accepted
time: 164ms
memory: 4020kb

input:

75 19

output:

967921272

result:

ok single line: '967921272'

Test #42:

score: 43
Accepted
time: 1092ms
memory: 3976kb

input:

124 9

output:

641081661

result:

ok single line: '641081661'

Test #43:

score: 43
Accepted
time: 164ms
memory: 3824kb

input:

76 66

output:

465902083

result:

ok single line: '465902083'

Test #44:

score: 43
Accepted
time: 1899ms
memory: 4164kb

input:

142 13

output:

12401929

result:

ok single line: '12401929'

Test #45:

score: 43
Accepted
time: 2317ms
memory: 4084kb

input:

150 5

output:

388058135

result:

ok single line: '388058135'

Test #46:

score: 43
Accepted
time: 673ms
memory: 4184kb

input:

109 97

output:

381109644

result:

ok single line: '381109644'

Test #47:

score: 43
Accepted
time: 2397ms
memory: 4136kb

input:

150 133

output:

174431234

result:

ok single line: '174431234'

Test #48:

score: 43
Accepted
time: 2314ms
memory: 4132kb

input:

150 147

output:

198921722

result:

ok single line: '198921722'

Test #49:

score: 43
Accepted
time: 2353ms
memory: 4088kb

input:

150 142

output:

631473185

result:

ok single line: '631473185'

Test #50:

score: 43
Accepted
time: 2391ms
memory: 4140kb

input:

150 136

output:

743180069

result:

ok single line: '743180069'

Test #51:

score: 43
Accepted
time: 2395ms
memory: 4284kb

input:

150 138

output:

621574340

result:

ok single line: '621574340'

Test #52:

score: 43
Accepted
time: 2484ms
memory: 4144kb

input:

150 119

output:

872660153

result:

ok single line: '872660153'

Test #53:

score: 43
Accepted
time: 2352ms
memory: 4136kb

input:

150 144

output:

939939060

result:

ok single line: '939939060'

Test #54:

score: 43
Accepted
time: 2303ms
memory: 4324kb

input:

150 1

output:

166208360

result:

ok single line: '166208360'

Test #55:

score: 43
Accepted
time: 2585ms
memory: 4148kb

input:

150 75

output:

353929212

result:

ok single line: '353929212'