QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#448684 | #8702. 狼人杀 | RedreamMer | 57 | 10ms | 13336kb | C++17 | 1.9kb | 2024-06-19 22:24:05 | 2024-06-19 22:24:05 |
Judging History
answer
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstdio>
#include <random>
#include <iomanip>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define PB emplace_back
#define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int) ((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) { rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1]; }
const int N = 50, mod = 1e9 + 7;
int a, b, f[N + 5][N + 5][N * N + 5][2];
bool vis[N + 5];
int qp(int n, int m = mod - 2) {
int res = 1;
for (; m; m >>= 1) {
if (m & 1) res = res * n % mod;
n = n * n % mod;
}
return res;
}
int S(int n) {return n * (n + 1) / 2 % mod;}
void add(int &n, int m) {
n += m;
if(n >= mod) n -= mod;
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> a >> b;
b = a - b + 1;
f[0][0][0][0] = mod - 1;
int sum = a * (a + 1) / 2 % mod;
rep(i, 0, a - 1) rep(j, 0, i) rep(k, 0, sum) rep(o, 0, 1) if(f[i][j][k][o]) {
add(f[i + 1][j][k + i + 1 - j][o], f[i][j][k][o]);
if(!o && i + 1 != b) add(f[i + 1][j][k + i + 1 - j][1], f[i][j][k][o]);
if(i + 1 != b) add(f[i + 1][i + 1][k][o], mod - f[i][j][k][o]);
}
int ans = 0;
rep(j, 0, a) rep(i, 0, sum - 1) if(f[a][j][i][1]) {
// cout << j << ' ' << i << ' ' << f[a][j][i][1] << endl;
(ans += f[a][j][i][1] * sum % mod * qp(sum - i + mod)) %= mod;
}
cout << ans * qp(a - 1) % mod;
return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 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: 4140kb
input:
12 2
output:
183756997
result:
ok single line: '183756997'
Test #2:
score: 23
Accepted
time: 1ms
memory: 4684kb
input:
17 6
output:
97571903
result:
ok single line: '97571903'
Test #3:
score: 23
Accepted
time: 0ms
memory: 4460kb
input:
13 3
output:
209826617
result:
ok single line: '209826617'
Test #4:
score: 23
Accepted
time: 1ms
memory: 4332kb
input:
13 8
output:
176038768
result:
ok single line: '176038768'
Test #5:
score: 23
Accepted
time: 0ms
memory: 4752kb
input:
18 4
output:
288404061
result:
ok single line: '288404061'
Test #6:
score: 23
Accepted
time: 1ms
memory: 4112kb
input:
10 10
output:
219657163
result:
ok single line: '219657163'
Test #7:
score: 23
Accepted
time: 1ms
memory: 4864kb
input:
19 15
output:
590577825
result:
ok single line: '590577825'
Test #8:
score: 23
Accepted
time: 0ms
memory: 4256kb
input:
11 6
output:
488143489
result:
ok single line: '488143489'
Test #9:
score: 23
Accepted
time: 1ms
memory: 4132kb
input:
10 5
output:
470594541
result:
ok single line: '470594541'
Test #10:
score: 23
Accepted
time: 1ms
memory: 4944kb
input:
20 5
output:
582458555
result:
ok single line: '582458555'
Test #11:
score: 23
Accepted
time: 1ms
memory: 4752kb
input:
20 12
output:
648081410
result:
ok single line: '648081410'
Test #12:
score: 23
Accepted
time: 1ms
memory: 4984kb
input:
20 4
output:
335777285
result:
ok single line: '335777285'
Test #13:
score: 23
Accepted
time: 2ms
memory: 4920kb
input:
20 15
output:
389216500
result:
ok single line: '389216500'
Test #14:
score: 23
Accepted
time: 0ms
memory: 4932kb
input:
20 16
output:
582458555
result:
ok single line: '582458555'
Test #15:
score: 23
Accepted
time: 1ms
memory: 4892kb
input:
20 19
output:
589126150
result:
ok single line: '589126150'
Test #16:
score: 23
Accepted
time: 1ms
memory: 4956kb
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: 4ms
memory: 12756kb
input:
49 14
output:
486918542
result:
ok single line: '486918542'
Test #18:
score: 34
Accepted
time: 2ms
memory: 6016kb
input:
28 13
output:
642223597
result:
ok single line: '642223597'
Test #19:
score: 34
Accepted
time: 0ms
memory: 7540kb
input:
35 23
output:
842346505
result:
ok single line: '842346505'
Test #20:
score: 34
Accepted
time: 4ms
memory: 11836kb
input:
47 11
output:
583647040
result:
ok single line: '583647040'
Test #21:
score: 34
Accepted
time: 0ms
memory: 7284kb
input:
34 30
output:
990970048
result:
ok single line: '990970048'
Test #22:
score: 34
Accepted
time: 0ms
memory: 6328kb
input:
30 7
output:
393675971
result:
ok single line: '393675971'
Test #23:
score: 34
Accepted
time: 3ms
memory: 10052kb
input:
43 5
output:
737421246
result:
ok single line: '737421246'
Test #24:
score: 34
Accepted
time: 0ms
memory: 6416kb
input:
30 21
output:
254760745
result:
ok single line: '254760745'
Test #25:
score: 34
Accepted
time: 0ms
memory: 5884kb
input:
27 22
output:
266692865
result:
ok single line: '266692865'
Test #26:
score: 34
Accepted
time: 5ms
memory: 9048kb
input:
40 12
output:
133652311
result:
ok single line: '133652311'
Test #27:
score: 34
Accepted
time: 0ms
memory: 6092kb
input:
29 4
output:
873892090
result:
ok single line: '873892090'
Test #28:
score: 34
Accepted
time: 10ms
memory: 13296kb
input:
50 46
output:
267950067
result:
ok single line: '267950067'
Test #29:
score: 34
Accepted
time: 6ms
memory: 13328kb
input:
50 11
output:
423642322
result:
ok single line: '423642322'
Test #30:
score: 34
Accepted
time: 10ms
memory: 13204kb
input:
50 43
output:
625476642
result:
ok single line: '625476642'
Test #31:
score: 34
Accepted
time: 6ms
memory: 13300kb
input:
50 36
output:
767166129
result:
ok single line: '767166129'
Test #32:
score: 34
Accepted
time: 0ms
memory: 13232kb
input:
50 14
output:
357467965
result:
ok single line: '357467965'
Test #33:
score: 34
Accepted
time: 5ms
memory: 13300kb
input:
50 30
output:
219673347
result:
ok single line: '219673347'
Test #34:
score: 34
Accepted
time: 10ms
memory: 13192kb
input:
50 44
output:
392786132
result:
ok single line: '392786132'
Test #35:
score: 34
Accepted
time: 6ms
memory: 13336kb
input:
50 10
output:
848251616
result:
ok single line: '848251616'
Subtask #3:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #36:
score: 0
Runtime Error
input:
75 47