QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#818061 | #8702. 狼人杀 | Sktn0089 | 100 ✓ | 2441ms | 35056kb | C++14 | 2.3kb | 2024-12-17 16:06:51 | 2024-12-17 16:06:52 |
Judging History
answer
#include <bits/stdc++.h>
namespace Initial {
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <int, int>
#define pb push_back
#define i128 __int128
using namespace std;
const ll maxn = 155, inf = 1e9, mod = 1e9 + 7;
ll power(ll a, ll b = mod - 2) {
ll s = 1;
while(b) {
if(b & 1) s = 1ll * s * a %mod;
a = 1ll * a * a %mod, b >>= 1;
} return s;
}
template <class T>
const inline ll pls(const T x, const T y) { return x + y >= mod? x + y - mod : x + y; }
template <class T>
const inline void add(T &x, const T y) { x = x + y >= mod? x + y - mod : x + y; }
template <class T>
const inline void chkmax(T &x, const T y) { x = x < y? y : x; }
template <class T>
const inline void chkmin(T &x, const T y) { x = x > y? y : x; }
} using namespace Initial;
namespace Read {
char buf[1 << 22], *p1, *p2;
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 22) - 10, stdin), p1 == p2)? EOF : *p1++)
template <class T>
const inline void rd(T &x) {
char ch; bool neg = 0;
while(!isdigit(ch = getchar()))
if(ch == '-') neg = 1;
x = ch - '0';
while(isdigit(ch = getchar()))
x = (x << 1) + (x << 3) + ch - '0';
if(neg) x = -x;
}
} using Read::rd;
ll n, m, f[maxn][maxn * maxn / 2][2], ans, a[maxn * maxn / 2];
signed main() {
rd(n), rd(m); ll P = n * (n + 1) / 2;
for(ll s = 1; s <= m; s++) {
memset(f, 0, sizeof f);
f[s][0][0] = mod - 1, f[s][0][1] = (mod - 1) * (s - 1) %mod;
for(ll i = s, lim = 0; i < n; lim += i - s, i++) {
for(ll j = 0; j <= lim; j++)
for(ll k = i + 1; k <= n; k++) {
if(i < m && k > m) break;
add(f[k][j + (((k - i) * (k - i - 1)) >> 1)][0], mod - f[i][j][0]);
add(f[k][j + (((k - i) * (k - i - 1)) >> 1)][1],
(mod - f[i][j][0]) * (k - i - 1) %mod);
add(f[k][j + (((k - i) * (k - i - 1)) >> 1)][1], mod - f[i][j][1]);
}
}
for(ll i = m, lim = (i - s) * (i - s - 1) / 2; i <= n; lim += i - s, i++)
for(ll j = 0; j <= lim; j++)
add(a[j + s * (n - i + 1) + s * (s - 1) / 2 + (n - i)
* (n - i + 1) / 2], (f[i][j][1] + f[i][j][0] * (n - i)) %mod);
}
for(ll i = 0; i < P; i++)
add(ans, P * power(P - i) %mod * a[i] %mod);
printf("%lld\n", ans * power(n - 1) %mod);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 23
Accepted
Test #1:
score: 23
Accepted
time: 6ms
memory: 34232kb
input:
12 2
output:
183756997
result:
ok single line: '183756997'
Test #2:
score: 23
Accepted
time: 8ms
memory: 34124kb
input:
17 6
output:
97571903
result:
ok single line: '97571903'
Test #3:
score: 23
Accepted
time: 4ms
memory: 33072kb
input:
13 3
output:
209826617
result:
ok single line: '209826617'
Test #4:
score: 23
Accepted
time: 17ms
memory: 33608kb
input:
13 8
output:
176038768
result:
ok single line: '176038768'
Test #5:
score: 23
Accepted
time: 3ms
memory: 32852kb
input:
18 4
output:
288404061
result:
ok single line: '288404061'
Test #6:
score: 23
Accepted
time: 15ms
memory: 34192kb
input:
10 10
output:
219657163
result:
ok single line: '219657163'
Test #7:
score: 23
Accepted
time: 26ms
memory: 33204kb
input:
19 15
output:
590577825
result:
ok single line: '590577825'
Test #8:
score: 23
Accepted
time: 13ms
memory: 34360kb
input:
11 6
output:
488143489
result:
ok single line: '488143489'
Test #9:
score: 23
Accepted
time: 13ms
memory: 33004kb
input:
10 5
output:
470594541
result:
ok single line: '470594541'
Test #10:
score: 23
Accepted
time: 8ms
memory: 33576kb
input:
20 5
output:
582458555
result:
ok single line: '582458555'
Test #11:
score: 23
Accepted
time: 26ms
memory: 33204kb
input:
20 12
output:
648081410
result:
ok single line: '648081410'
Test #12:
score: 23
Accepted
time: 6ms
memory: 33208kb
input:
20 4
output:
335777285
result:
ok single line: '335777285'
Test #13:
score: 23
Accepted
time: 25ms
memory: 33536kb
input:
20 15
output:
389216500
result:
ok single line: '389216500'
Test #14:
score: 23
Accepted
time: 22ms
memory: 33236kb
input:
20 16
output:
582458555
result:
ok single line: '582458555'
Test #15:
score: 23
Accepted
time: 27ms
memory: 33312kb
input:
20 19
output:
589126150
result:
ok single line: '589126150'
Test #16:
score: 23
Accepted
time: 11ms
memory: 34160kb
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: 33ms
memory: 33160kb
input:
49 14
output:
486918542
result:
ok single line: '486918542'
Test #18:
score: 34
Accepted
time: 28ms
memory: 34380kb
input:
28 13
output:
642223597
result:
ok single line: '642223597'
Test #19:
score: 34
Accepted
time: 48ms
memory: 34520kb
input:
35 23
output:
842346505
result:
ok single line: '842346505'
Test #20:
score: 34
Accepted
time: 27ms
memory: 33780kb
input:
47 11
output:
583647040
result:
ok single line: '583647040'
Test #21:
score: 34
Accepted
time: 63ms
memory: 33552kb
input:
34 30
output:
990970048
result:
ok single line: '990970048'
Test #22:
score: 34
Accepted
time: 13ms
memory: 34784kb
input:
30 7
output:
393675971
result:
ok single line: '393675971'
Test #23:
score: 34
Accepted
time: 12ms
memory: 33112kb
input:
43 5
output:
737421246
result:
ok single line: '737421246'
Test #24:
score: 34
Accepted
time: 29ms
memory: 34140kb
input:
30 21
output:
254760745
result:
ok single line: '254760745'
Test #25:
score: 34
Accepted
time: 31ms
memory: 34244kb
input:
27 22
output:
266692865
result:
ok single line: '266692865'
Test #26:
score: 34
Accepted
time: 25ms
memory: 34884kb
input:
40 12
output:
133652311
result:
ok single line: '133652311'
Test #27:
score: 34
Accepted
time: 10ms
memory: 34124kb
input:
29 4
output:
873892090
result:
ok single line: '873892090'
Test #28:
score: 34
Accepted
time: 100ms
memory: 34052kb
input:
50 46
output:
267950067
result:
ok single line: '267950067'
Test #29:
score: 34
Accepted
time: 30ms
memory: 33280kb
input:
50 11
output:
423642322
result:
ok single line: '423642322'
Test #30:
score: 34
Accepted
time: 78ms
memory: 32856kb
input:
50 43
output:
625476642
result:
ok single line: '625476642'
Test #31:
score: 34
Accepted
time: 47ms
memory: 34848kb
input:
50 36
output:
767166129
result:
ok single line: '767166129'
Test #32:
score: 34
Accepted
time: 23ms
memory: 34364kb
input:
50 14
output:
357467965
result:
ok single line: '357467965'
Test #33:
score: 34
Accepted
time: 48ms
memory: 33788kb
input:
50 30
output:
219673347
result:
ok single line: '219673347'
Test #34:
score: 34
Accepted
time: 74ms
memory: 32940kb
input:
50 44
output:
392786132
result:
ok single line: '392786132'
Test #35:
score: 34
Accepted
time: 34ms
memory: 34536kb
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: 159ms
memory: 33428kb
input:
75 47
output:
668751416
result:
ok single line: '668751416'
Test #37:
score: 43
Accepted
time: 150ms
memory: 34412kb
input:
75 41
output:
310834114
result:
ok single line: '310834114'
Test #38:
score: 43
Accepted
time: 1205ms
memory: 35056kb
input:
133 124
output:
57167600
result:
ok single line: '57167600'
Test #39:
score: 43
Accepted
time: 1021ms
memory: 33612kb
input:
129 74
output:
751074385
result:
ok single line: '751074385'
Test #40:
score: 43
Accepted
time: 1538ms
memory: 34296kb
input:
135 133
output:
759430862
result:
ok single line: '759430862'
Test #41:
score: 43
Accepted
time: 102ms
memory: 34552kb
input:
75 19
output:
967921272
result:
ok single line: '967921272'
Test #42:
score: 43
Accepted
time: 317ms
memory: 34944kb
input:
124 9
output:
641081661
result:
ok single line: '641081661'
Test #43:
score: 43
Accepted
time: 170ms
memory: 33128kb
input:
76 66
output:
465902083
result:
ok single line: '465902083'
Test #44:
score: 43
Accepted
time: 791ms
memory: 34684kb
input:
142 13
output:
12401929
result:
ok single line: '12401929'
Test #45:
score: 43
Accepted
time: 433ms
memory: 34796kb
input:
150 5
output:
388058135
result:
ok single line: '388058135'
Test #46:
score: 43
Accepted
time: 472ms
memory: 33460kb
input:
109 97
output:
381109644
result:
ok single line: '381109644'
Test #47:
score: 43
Accepted
time: 1806ms
memory: 32988kb
input:
150 133
output:
174431234
result:
ok single line: '174431234'
Test #48:
score: 43
Accepted
time: 2441ms
memory: 34280kb
input:
150 147
output:
198921722
result:
ok single line: '198921722'
Test #49:
score: 43
Accepted
time: 2163ms
memory: 34672kb
input:
150 142
output:
631473185
result:
ok single line: '631473185'
Test #50:
score: 43
Accepted
time: 1898ms
memory: 34844kb
input:
150 136
output:
743180069
result:
ok single line: '743180069'
Test #51:
score: 43
Accepted
time: 1951ms
memory: 34304kb
input:
150 138
output:
621574340
result:
ok single line: '621574340'
Test #52:
score: 43
Accepted
time: 1629ms
memory: 34844kb
input:
150 119
output:
872660153
result:
ok single line: '872660153'
Test #53:
score: 43
Accepted
time: 2262ms
memory: 34164kb
input:
150 144
output:
939939060
result:
ok single line: '939939060'
Test #54:
score: 43
Accepted
time: 99ms
memory: 33688kb
input:
150 1
output:
166208360
result:
ok single line: '166208360'
Test #55:
score: 43
Accepted
time: 2181ms
memory: 33736kb
input:
150 75
output:
353929212
result:
ok single line: '353929212'