QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#525726 | #8702. 狼人杀 | Fido_Puppy | 100 ✓ | 2585ms | 4324kb | C++23 | 4.8kb | 2024-08-20 21:10:19 | 2024-08-20 21:10:19 |
Judging History
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'