Loj #3102. 「JSOI2019」神经网络

题目背景

火星探险队发现，火星人的思维方式与人类非常不同，是因为他们拥有与人类很不一样的神经网络结构。为了更好地理解火星人的行为模式，JYY 对小镇上火星人的大脑进行了扫描，得到了一些重要数据。

题目描述

火星人在出生后，神经网络可以看作是一个由若干无向树 \(\{T_1(V_1, E_1), T_2(V_2, E_2),\ldots T_m(V_m, E_m)\}\) 构成的森林。随着火星人年龄的增长，神经连接的数量也不断增长。初始时，神经网络中生长的连接 \(E^\ast = \emptyset\)。神经网络根据如下规则生长：

- 如果节点 \(u \in V_i, v \in V_j\) 分别属于不同的无向树 \(T_i\) 和 \(T_j\ (i \neq j)\)，则 \(E^\ast\) 中应当包含边 \((u, v)\)。

最终，在不再有神经网络连接可能生长后，神经网络之间的节点连接可以看成是一个无向图 \(G(V,E)\)，其中

\[V=V_1\cup V_2\cup \ldots \cup V_m,E=E_1\cup E_2\cup \ldots \cup E_m\cup E^\ast\]

火星人的决策是通过在 \(G(V, E)\) 中建立环路完成的。针对不同的外界输入，火星人会建立不同的神经连接环路，从而做出不同的响应。为了了解火星人行为模式的复杂性，JYY 决定计算 \(G\) 中哈密顿回路的数量。

\(G(V, E)\) 的哈密顿回路是一条简单回路，从第一棵树的第一个节点出发，恰好经过 \(V\) 中的其他节点一次且仅一次，并且回到第一棵树的第一个节点。

输入格式

第一行读入 \(m\)，表示火星人神经网络初始时无向树的数量。

接下来输入有 \(m\) 部分，第 \(i\) 部分描述了树 \(T_i\)。

对于 \(T_i\)，输入的第一行是树 \(T_i(V_i, E_i)\) 中节点的数量 \(k_i\)。假设 \(V_i = \{v1_, v_2,\ldots ,v_{k_i}\}\)。

接下来 \(k_{i} - 1\) 行，每行两个整数 \(x, y\)，表示该树节点 \(v_x, v_y\ (1 \le x, y \le k_i)\) 之间有一条树边，即 \((v_x, v_y) \in E_i\)。

输出格式

因为哈密顿回路的数量可能很多，你只需要输出一个非负整数，表示答案对 \(998244353\) 取模后的值。

数据范围与提示

\(\sum_{i=1}^m k_i\le 5\times 10^3,m\leq 300\)

\(\\\)

一个合法情况可以这样来看：将第\(i\)棵树分为\(k_i\)条不相交链，且这些链的并是第\(i\)棵树，然后将这些链排列起来，相邻的链不能来自同一颗树。特别地，第\(1\)棵树的\(1\)号点所在的链要拆成两半分别放在排列的两端。

首先对于每颗树，\(DP\)出来选\(i\)条链的方案数，这个\(DP\)就设\(f_{i,j,0/1/2}\)表示以\(i\)为根的子树中，\(i\)所在的链点数为\(1\)/点数\(>1\)且没有分叉/有分叉的方案数。每种方案还要\(*2^k\)，其中\(k\)是点数\(>1\)的链的数量（因为正反都可以）。

接着考虑用容斥来算答案。设\(S_{i,j}\)表示将\(i\)个元素分为\(j\)个排列的方案数。这个可以考虑先\(DP\)出“将长度为\(i\)的序列分成\(j\)段”的方案数，再\(*i!\)。对于第\(m\)棵树,有\(n\)个点，假设我们选出了\(i\)条链的方案数为\(G_i\)。我们要强制有\(j\)对链是相邻的，那么答案是\(S_{i,i-j}*G_i\)，容斥系数是\((-1)^{j}\)。于是我们可以预处理出\(H\)数组，\(H_i\)表示选出来的链有\(i\)段的系数：

\[ H_i=\sum_{j=i}^n (-1)^{j-i} G_i*S_{i,j} \]

注意第\(1\)棵树第\(1\)个点要特殊处理。最后在将每颗树选出来的许多连续段随便排列，这个可以用背包实现。

代码：

#include
    
     #define ll long long#define M 305#define N 5005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}const ll mod=998244353;ll ksm(ll t,ll x) {    ll ans=1;    for(;x;x>>=1,t=t*t%mod)        if(x&1) ans=ans*t%mod;    return ans;}const ll inv2=mod+1>>1;int m;int n;struct road {int to,nxt;}s[N<<1];int h[N],cnt;void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}ll fac[N],ifac[N];ll C(int n,int m) {return n
     
      =0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;    S[0][0]=1;    for(int j=1;j<=n;j++) {        ll pre=0;        for(int i=j;i<=n;i++) {            (pre+=S[i-1][j-1])%=mod;            S[i][j]=pre;        }    }    for(int i=0;i<=n;i++) {        for(int j=0;j<=i;j++) {            S[i][j]=S[i][j]*fac[i]%mod;            if(i-j&1) S[i][j]=(mod-S[i][j])%mod;        }    }}int main() {    pre(5000);    m=Get();    for(int now=1;now<=m;now++) {        n=Get();        Init();        for(int j=1;j
      
       1) (F[1][j]+=G[i+1]*S[i][j])%=mod;                }            }        } else {            for(int i=1;i<=n;i++) {                G[i]=(f[0][1][i]+f[1][1][i]+f[2][1][i])%mod;            }            for(int i=0;i<=n;i++) H[i]=0;            for(int i=1;i<=n;i++) {                for(int j=1;j<=i;j++) {                    (H[j]+=G[i]*S[i][j])%=mod;                }            }            for(int j=2;j<=tot;j++) {                for(int k=1;k<=n;k++) {                    (F[now][j+k]+=F[now-1][j]*H[k]%mod*C(j-2+k,k))%=mod;                }            }            tot+=n;        }    }    ll Ans=0;    for(int i=2;i<=tot;i++) (Ans+=F[m][i])%=mod;    cout<