QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#384645#2438. Minimum Spanning Treesjames1BadCreeperRE 0ms0kbC++141.7kb2024-04-10 08:28:132024-04-10 08:28:13

Judging History

你现在查看的是最新测评结果

  • [2024-04-10 08:28:13]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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...

output:


result: