提出 #50056781

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x) 
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 3e3 + 10;
const int Mod = 998244353;

void add_mod(int &x, int y) {
    x += y;
    if (x >= Mod) {
        x -= Mod;
    }
}

int n;
vector<int> G[MAXN];
int fac[MAXN];
int f[MAXN][MAXN], tmp[MAXN], g[MAXN][2];

void dfs(int u, int fa) {
    f[u][0] = 1;
    for (auto v : G[u]) {
        if (v == fa) {
            continue;
        }
        dfs(v, u);
        memcpy(tmp, f[u], sizeof(tmp));
        memset(f[u], 0, sizeof(f[u]));
        for (int i = n - 1; i >= 1; i--) {
            add_mod(f[u][i], 1ll * tmp[i - 1] * g[v][1] % Mod);
        }
        for (int i = n - 1; i >= 0; i--) {
            add_mod(f[u][i], 1ll * tmp[i] * g[v][0] % Mod);
        }
    }

    for (int i = 0; i < n; i++) {
        add_mod(g[u][0], 1ll * f[u][i] * fac[i] % Mod);
        add_mod(g[u][1], 1ll * f[u][i] * fac[i + 1] % Mod);
    }
}

void solve() {
	cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = 1ll * fac[i - 1] * i % Mod;
    }
    dfs(1, 0);
    int ans = g[1][0];
    cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	int T = 1;
	while (T--) solve();
	return 0;
}

提出情報

ジャッジ結果