LOJ#3102. 「JSOI2019」神经网络
首先我们容易发现就是把树拆成若干条链，然后要求这些链排在一个环上，同一棵树的链不相邻
把树拆成链可以用一个简单（但是需要复杂的分类讨论）的树背包实现
(dp[u][j][0/1/2])表示第(u)个点已经选了(j)条链，0是两个不同子树的链拼到一起，1是只有1个点，2是有一条至少有两个点的链
通过这个我们可以求一个(f[k])表示把这棵树分成(k)条链有几种情况
环排列可以通过全排列除以排列长度得到
我们设把(k)条链分成(h)个小块，这样我们至少有了(k - h)对点同一棵树且相邻，容斥系数乘上((-1)^{k - h})，对于全排列来说，我们还需要除以(h!)
所以列出一个这样的EGF
(f[k]k!inom{k - 1}{h - 1} frac{x^{h}}{h!})
就可以卷积了
然后对于答案的(x^{h})乘上((h - 1)!)因为是环排
就可以得到答案
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define ba 47
#define MAXN 5005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const int MOD = 998244353,MAXL = (1 << 15);
int W[MAXL + 5];
int fac[100005],invfac[100005];
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
void update(int &x,int y) {
x = inc(x,y);
}
int fpow(int x,int c) {
int res = 1,t = x;
while(c) {
if(c & 1) res = mul(res,t);
t = mul(t,t);
c >>= 1;
}
return res;
}
int C(int n,int m) {
if(n < m) return 0;
else return mul(fac[n],mul(invfac[m],invfac[n - m]));
}
void NTT(vector<int> &f,int l,int on) {
f.resize(l);
for(int i = 1,j = l >> 1 ; i < l - 1 ; ++i) {
if(i < j) swap(f[i],f[j]);
int k = l >> 1;
while(j >= k) {
j -= k;
k >>= 1;
}
j += k;
}
for(int h = 2 ; h <= l ; h <<= 1) {
int wn = W[(MAXL + on * MAXL / h) % MAXL];
for(int k = 0 ; k < l ; k += h) {
int w = 1;
for(int j = k ; j < k + h / 2 ; ++j) {
int u = f[j],t = mul(w,f[j + h / 2]);
f[j] = inc(u,t);
f[j + h / 2] = inc(u,MOD - t);
w = mul(w,wn);
}
}
}
if(on == -1) {
int invL = fpow(l,MOD - 2);
for(int i = 0 ; i < l ; ++i) f[i] = mul(f[i],invL);
}
}
vector<int> operator * (vector<int> a,vector<int> b) {
vector<int> c;
int l = 1;
while(l <= a.size() - 1 + b.size() - 1) l <<= 1;
NTT(a,l,1);NTT(b,l,1);
c.resize(l);
for(int i = 0 ; i < l ; ++i) c[i] = mul(a[i],b[i]);
NTT(c,l,-1);
int s = c.size() - 1;
while(s > 0) {
if(c[s] == 0) {c.pop_back();--s;}
else break;
}
return c;
}
void Init() {
W[0] = 1;W[1] = fpow(3,(MOD - 1) / MAXL);
for(int i = 2 ; i < MAXL ; ++i) W[i] = mul(W[i - 1],W[1]);
fac[0] = 1;
for(int i = 1 ; i <= 100000 ; ++i) fac[i] = mul(fac[i - 1],i);
invfac[100000] = fpow(fac[100000],MOD - 2);
for(int i = 99999 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1);
}
int M,K;
struct node {
int to,next;
}E[100005];
int head[5005],sumE,siz[5005];
int dp[5005][5005][3],g[5005][3],f[5005],all;
vector<int> z,ans;
void add(int u,int v) {
E[++sumE].to = v;
E[sumE].next = head[u];
head[u] = sumE;
}
void dfs(int u,int fa) {
dp[u][0][1] = 1;
siz[u] = 1;
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa) {
dfs(v,u);
for(int j = 0 ; j <= siz[u] + siz[v] ; ++j) memset(g[j],0,sizeof(g[j]));
for(int j = 0 ; j <= siz[u] ; ++j) {
for(int h = 0 ; h <= siz[v] ; ++h) {
int t0 = inc(dp[v][h][1],mul(dp[v][h][2],2));
int t1 = inc(dp[v][h][1],dp[v][h][2]);
update(g[j + h][0],mul(dp[u][j][0],dp[v][h][0]));
update(g[j + h + 1][0],mul(dp[u][j][0],t0));;
update(g[j + h][1],mul(dp[u][j][1],dp[v][h][0]));
update(g[j + h + 1][1],mul(dp[u][j][1],t0));
update(g[j + h][2],mul(dp[u][j][1],t1));
update(g[j + h][2],mul(dp[u][j][2],dp[v][h][0]));
update(g[j + h + 1][2],mul(dp[u][j][2],t0));
update(g[j + h + 1][0],mul(dp[u][j][2],mul(2,t1)));
}
}
siz[u] += siz[v];
for(int j = 0 ; j <= siz[u] ; ++j) {
for(int h = 0 ; h < 3 ; ++h) {
dp[u][j][h] = g[j][h];
}
}
}
}
if(!fa) {
memset(f,0,sizeof(f));
for(int j = 0 ; j <= siz[1] ; ++j) {
update(f[j],dp[1][j][0]);
update(f[j + 1],dp[1][j][1]);
update(f[j + 1],mul(2,dp[1][j][2]));
}
}
}
void Solve() {
read(M);
ans.pb(1);
for(int i = 1 ; i <= M ; ++i) {
sumE = 0;
memset(head,0,sizeof(head));
memset(siz,0,sizeof(siz));
for(int j = 0 ; j <= K ; ++j) {
for(int h = 0 ; h <= K ; ++h) {
memset(dp[j][h],0,sizeof(dp[j][h]));
}
}
read(K);
all += K;
int a,b;
for(int j = 1 ; j < K ; ++j) {
read(a);read(b);
add(a,b);add(b,a);
}
dfs(1,0);
z.clear();
z.resize(K + 1);
for(int j = K ; j >= 1 ; --j) {
int a = mul(f[j],fac[j]);
for(int h = j ; h >= 1 ; --h) {
int t = mul(a,C(j - 1,h - 1));
if((j - h) & 1) t = MOD - t;
update(z[h],t);
}
}
for(int j = 0 ; j <= K ; ++j) z[j] = mul(z[j],invfac[j]);
ans = ans * z;
}
int res = 0;
for(int i = 1 ; i <= all ; ++i) {
update(res,mul(ans[i],fac[i - 1]));
}
out(res);enter;
}
int main(){
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}