QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#851767 | #8702. 狼人杀 | Xiaohuba | 100 ✓ | 3484ms | 104660kb | C++23 | 5.2kb | 2025-01-10 23:43:48 | 2025-01-10 23:43:50 |
Judging History
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; }
詳細信息
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'