数树题。
[ARC155F] Directable as Desired
给定长度为 \(N\) 的非负整数序列 \(D=(D_1,D_2,\dots,D_N)\)，满足 \(\sum_{i=1}^N D_i=N-1\)。
统计有多少带标号无根树，节点编号 \(1 \sim N\)，满足以下条件：
- 存在一种将 \(N-1\) 条边分别定向的方案，使得节点 \(i\) 的出度为 \(D_i\)。
输出答案对 \(998244353\) 取模后的结果。
数据范围：\(2 \le N \le 2 \times 10^5\)。
有标号无根树比较抽象，所以转化成点边均有标号的有根树求解。
一棵有标号无根树转化为点边均有标号的有根树的方案数是 \(n\prod d_i\)，留着备用。
把根搞出来后，每条边的方向就分成两种，一种是向上即向根节点方向、一种是向下即向叶子节点方向。
考虑指定一个集合 \(S\) 满足仅有 \(S\) 节点与其父亲节点的边是向上的。设 \(m = |S|\)。
然后指定这些点是哪条边连向父亲节点，这里的方案数是 \(\prod_{i \in S} d_i\)。
那么现在我们依次考虑指定向上的边的方案数和向下的边的方案数。
先看向上的边。因为仅对于 \(S\) 中的点才会产生一条这样的边，所以最后会形成的是 \(n\) 个点 \(m\) 条边的内向树森林。
森林不好算，所以指定一个超级点 \(0\)，让所有内向树根连向 \(0\)。
这样就是要对 \(0\) 的度数为 \(n - m\) 的内向树计数。
把边的方向忽视后就是对 \(0\) 节点度数为 \(n - m\) 的无根树计数。
转化为 Prufer 序列后就是 \(0\) 号节点出现 \(n - m - 1\) 次的序列计数，这一部分的答案为：
\[n^m \binom {n - 1}{n - m - 1} \]但是这个答案包含了指定 \(S\) 集合的方案数，而到这一步我们的 \(S\) 集合是已知的，所以要除以一个 \(\binom nm\)。
所以这一部分的答案为
\[n ^ {m - 1} (n - m) \]最后考虑向下的边的方案数。
因为每条边都有编号，所以按照编号依次连边。
经过了上面的步骤我们得到了 \(n\) 个点 \(m\) 条边的内向树森林。每条边不能连向自己的祖先，不能连向向上连了边的点。连第一条边时有 \(n - m - 1\) 种方案，然后此时连通块少了一个。以此类推，连第 \(i\) 条边的时候我们有 \(n - m - i\) 种选择。综上这一部分的方案数是
\[(n - m - 1)! \]把这三部分的答案整合起来得到点边标号的有根树的答案：
\[\sum _{m = 0} ^{n - 1} (n - m - 1)! \cdot n ^ {m - 1} (n - m) \cdot \sum _{|S| = m} \prod _ {i \in S} d_i \\ =\sum_{m = 0} ^{n - 1} (n - m) ! \cdot n ^ {m - 1} \cdot [x^m] \prod _{i = 1} ^n (1 + d_ix) \]后面的部分分治 NTT 即可。最后答案除以 \(n\prod d_i\) 就行了。
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
namespace Poly{
using poly = vector<int>;
const int G = 3, P = 998244353;
const int inv2 = 499122177;
int Ksm(int u, int v){
int ret = 1;
while(v){
if(v & 1) ret = 1ll * ret * u % P;
u = 1ll * u * u % P, v >>= 1;
}
return ret;
}
int NTT(poly &A, int N){
int d = N >> 1;
poly trn;
trn.push_back(0);
trn.push_back(d);
for(int w = 2; w <= N; w <<= 1){
d >>= 1;
for(int c = 0; c < w; c ++)
trn.push_back(trn[c] | d);
}
for(int i = 1; i < N; i ++)
if(trn[i] > i)
swap(A[i], A[trn[i]]);
for(int len = 2, M = 1; len <= N; M = len, len <<= 1){
int W;
W = Ksm(G, (P - 1) / len);
for(int l = 0; l <= N - len + 1; l += len){
auto w0 = 1;
for(int nw = l; nw < l + M; nw ++){
int x = A[nw], y = 1ll * w0 * A[nw + M] % P;
A[nw] = (x + y) % P, A[nw + M] = (x - y + P) % P;
w0 = 1ll * w0 * W % P;
}
}
}
return 0;
}
poly convolution(poly a, poly b){
int n = a.size(), m = b.size();
if(!n || !m)
return {};
int sm = n + m - 1;
int k = 1;
while(k < sm)
k <<= 1;
a.resize(k), b.resize(k);
NTT(a, k);
NTT(b, k);
for(int i = 0; i < k; i ++)
a[i] = 1ll * a[i] * b[i] % P;
NTT(a, k);
reverse(++ a.begin(), a.end());
int invk = Ksm(k, P - 2);
for(int i = 0; i < a.size(); i ++)
a[i] = 1ll * a[i] * invk % P;
a.resize(n + m - 1);
return a;
}
poly polyInv(poly f){
int n = f.size();
int k = 1;
while(k < n)
k <<= 1;
k <<= 1;
poly g;
f.resize(k);
g.push_back(Ksm(f[0], P - 2));
for(int len = 2; len <= k; len <<= 1){
int M = len >> 1;
poly tmp2, tmp1;
for(int i = 0; i < M; i ++)
tmp2.push_back(g[i]);
for(int i = 0; i < M; i ++)
tmp1.push_back(f[i]);
tmp1.resize(len);
tmp2 = convolution(tmp2, tmp2);
tmp2 = convolution(tmp1, tmp2);
for(int i = 0; i < M; i ++)
g[i] = (2ll * g[i] % P + P - tmp2[i]) % P;
for(int i = M; i < len; i ++)
g.push_back((2ll * g[i] % P + P - tmp2[i]) % P);
}
g.resize(n);
return g;
}
poly polyDev(poly f){
poly g;
int k = f.size();
for(int i = 1; i < k; i ++)
g.push_back(1ll * i * f[i] % P);
g.resize(k - 1);
return g;
}
poly polyInDev(poly f){
poly g;
int k = f.size();
g.push_back(0);
for(int i = 1; i < k; i ++)
g.push_back(1ll * f[i - 1] * Ksm(i, P - 2) % P);
return g;
}
poly polyLn(poly a){
int n = a.size();
poly b = a;
a = polyDev(a);
b = polyInv(b);
a = convolution(a, b);
a = polyInDev(a);
a.resize(n);
return a;
}
int polyOutput(poly a){
for(int i = 0; i < a.size(); i ++)
cout << a[i] << " ";
cout << "\n";
return 0;
}
poly polyExp(poly f){
int n = f.size();
int k = 1;
while(k < n)
k <<= 1;
k <<= 1;
poly g;
f.resize(k);
g.push_back(1);
for(int len = 2; len <= k; len <<= 1){
int M = len >> 1;
poly tmp2;
for(int i = 0; i < M; i ++)
tmp2.push_back(g[i]);
auto tmp3 = polyLn(tmp2);
for(int i = 0; i < M; i ++)
tmp3[i] = (((P - tmp3[i] + f[i]) % P) + P) % P;
tmp3[0] ++;
tmp3[0] %= P;
tmp2 = convolution(tmp3, tmp2);
for(int i = 0; i < M; i ++)
g[i] = tmp2[i];
for(int i = M; i < len; i ++)
g.push_back(tmp2[i]);
}
g.resize(n);
return g;
}
poly polyPow(poly a, int k){
int n = a.size();
int t = 0;
for(int i = 0; i < n; i ++){
if(a[t] != 0) break;
t ++;
}
if(t == n) return a;
int r = Ksm(a[t], P - 2);
poly b;
for(int i = t; i < n; i ++)
b.push_back(1ll * a[i] * r % P);
a.resize(t);
int m = b.size();
b = polyLn(b);
for(int i = 0; i < m; i ++)
b[i] = 1ll * b[i] * k % P;
b = polyExp(b);
for(int i = 0; i < m; i ++)
a.push_back(b[i]);
return a;
}
}
namespace azus{
using namespace Poly;
int n;
int d[200005];
poly a;
vector<int> calc(vector<int> &a, int l, int r) {
if (r - l == 1)
return {1, a[l]};
int mid = (l + r) >> 1;
return convolution(calc(a, l, mid), calc(a, mid, r));
}
int ans = 0;
int jc[200005], inv[200005];
int main(){
cin >> n;
jc[0] = inv[0] = 1;
for(int i = 1; i <= n; i ++)
jc[i] = jc[i - 1] * i % P;
inv[n] = Ksm(jc[n], P - 2);
for(int i = n - 1; i >= 1; i --)
inv[i] = inv[i + 1] * (i + 1) % P;
for(int i = 1; i <= n; i ++)
cin >> d[i], a.push_back(d[i]);
a = calc(a, 0, n);
ans = jc[n - 1];
for(int m = 1; m < n; m ++)
(ans += (jc[n - m] * Ksm(n, m - 1) % P) * a[m] % P) %= P;
ans = ans * Ksm(n, P - 2) % P;
for(int i = 1; i <= n; i ++)
ans = ans * inv[d[i]] % P;
cout << ans << "\n";
return 0;
}
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
int T = 1;
while(T --) azus::main();
return 0;
}