QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#384645 | #2438. Minimum Spanning Trees | james1BadCreeper | RE | 0ms | 0kb | C++14 | 1.7kb | 2024-04-10 08:28:13 | 2024-04-10 08:28:13 |
answer
#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
inline int poww(int a, int b) {
int r = 1;
for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) r = 1ll * r * a % P;
return r;
}
inline int inv(int x) { return poww(x, P - 2); }
int n, k, p[10];
int f[45][170], g[45][170], C[45][45];
int main(void) {
freopen("mst.in", "r", stdin);
freopen("mst.out", "w", stdout);
for (int i = 0; i <= 44; ++i)
for (int j = C[i][0] = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
cin >> n >> k;
for (int i = 0; i <= k; ++i) cin >> p[i], p[i] = 1ll * p[i] * inv(100) % P;
p[k + 1] = p[0];
for (int i = k; i >= 1; --i) p[i] = (p[i] + p[i + 1]) % P;
f[1][0] = 1;
for (int t = 1; t <= k; ++t) {
memset(g, 0, sizeof g);
for (int i = 1; i <= n; ++i) for (int j = 0; j <= (i - 1) * t; ++j) {
g[i][j] = f[i][j];
for (int x = 1; x < i; ++x) for (int y = 0; y + t <= j; ++y)
g[i][j] = (g[i][j] + 1ll * g[i - x][j - y - t] * f[x][y] % P * poww(p[t], x * (i - x)) % P * C[i - 1][x - 1]) % P;
}
memset(f, 0, sizeof f);
for (int i = 1; i <= n; ++i) for (int j = 0; j <= (i - 1) * t; ++j) {
f[i][j] = g[i][j];
for (int x = 1; x < i; ++x) for (int y = 0; y + t <= j; ++y)
f[i][j] = (f[i][j] - 1ll * g[i - x][j - y - t] * f[x][y] % P * poww(p[t + 1], x * (i - x)) % P * C[i - 1][x - 1]) % P;
}
}
for (int i = n - 1; i <= k * (n - 1); ++i) cout << (f[n][i] + P) % P << " \n"[i == k * (n - 1)];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
200 3 1 50 50 3 2 0 50 50 3 3 25 25 25 25 8 1 41 59 7 3 37 30 7 26 3 3 16 12 18 54 9 2 9 43 48 9 3 3 40 42 15 9 1 29 71 9 2 40 42 18 5 1 76 24 5 1 39 61 9 2 23 38 39 10 4 18 15 34 2 31 7 2 23 28 49 9 4 15 13 25 19 28 7 1 64 36 6 1 50 50 9 1 4 96 4 1 64 36 9 2 24 45 31 9 2 3 61 36 9 1 65 35 8 4 6 1 3...