Endless Pallet

The input starts with one line containing exactly one integer T, which is the number of test cases.

Each test case starts with one line containing exactly one integer N, indicating the size of the tree.

Then followed by N lines, each consists of 2 numbers u_i, v_i, indicating the i-th edge of the tree is between u_i and v_i.
- 1 ≤ T ≤ 15.
- 1 ≤ N ≤ 50.
- 1 ≤ u_i, v_i ≤ n.

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the expected number of the paths Ash choose.

In order to avoid floating point arithmetic, you are supposed to output y modulo 998244353, that means if the answer is equal to $\frac{P}{Q}$ , you should output $y = P \cdot Q^{-1} \mod 998244353$ .

C++ 解法, 执行用时: 143ms, 内存消耗: 29164K, 提交时间: 2021-10-06 17:10:11

#include <bits/stdc++.h>

#define fp(i, a, b) for(int i = a, i##_ = (b) + 1; i < i##_; ++i)
using namespace std;
using ll = int64_t;
const int N = 52, M = N * (N + 1) / 2, P = 998244353;
int n, sz[N], inv[M], f[N][N][M][2], g[N][M][2];
vector<int> G[N];
#define MUL(a, b) ((ll) (a) * (b) % P)
#define ADD(a, b) (((a) += (b)) >= P ? (a) -= P : 0) // (a += b) %= P
int C2(int x) { return x * (x - 1) >> 1; }
void Merge(int a[N][M][2], int b[N][M][2], int A, int B) {
    fp(i, 0, A + B) memset(g[i], 0, 8 * (C2(A + B + 1) + 1));
    fp(i, 0, A) fp(j, 0, C2(A + 1)) fp(k, 0, 1) if (a[i][j][k])
        fp(x, 0, B) fp(y, 0, C2(B + 1)) fp(z, 0, 1) if (b[x][y][z])
            ADD(g[i ? i + x : 0][j + y + i * x][k ^ z], MUL(a[i][j][k], b[x][y][z]));
    fp(i, 0, A + B) memcpy(a[i], g[i], 8 * (C2(A + B + 1) + 1));
}
void dfs(int u, int p) {
    sz[u] = f[u][1][1][0] = f[u][0][0][1] = 1;
    for (auto v: G[u]) if (v != p)
        dfs(v, u), Merge(f[u], f[v], sz[u], sz[v]), sz[u] += sz[v];
}
void Solve() {
    fp(i, 1, n) G[i].clear();
    fp(i, 0, n) fp(j, 0, n) memset(f[i][j], 0, 8 * (C2(n + 1) + 1));
    for (int u, v, i = 1; i < n; ++i)
        scanf("%d%d", &u, &v),
        G[u].push_back(v), G[v].push_back(u);
    dfs(1, 0);
    ll ans = 0, s = C2(n + 1);
    fp(i, 0, n) fp(j, 0, s - 1) fp(k, 0, 1)
        ans += (k ? 1 : -1) * s * inv[s - j] % P * f[1][i][j][k] % P;
    printf("%lld\n", (ans % P + P) % P);
}
int main() {
    inv[1] = 1;
    fp(i, 2, M - 1) inv[i] = (ll) (P - P / i) * inv[P % i] % P;
    scanf("%*d");
    for (int i = 1; ~scanf("%d", &n); ++i)
        printf("Case #%d: ", i), Solve();
    return 0;
}

详情