「JSOI2019」神经网络

考虑一个合法的哈密顿路可以表示为什么样子：

按照不同树的编号，分割为一段段，相邻两段属于不同树

同时，如果最后一段和第一段同编号，将最后一段移动到第一段前面

由此，一个哈密顿路可以由唯一表示：

1号点在第一个段中，此后每一段和上一个属于不同树，且最后一段不属于1树

由此，问题分解为两部分：

Part1 求解树路径分段

考虑树形\(dp\)求解，每个点记录\(dp_{i,j,0/1}\)表示当前\(i\)子树内已经产生\(j\)条路径，\(i\)自己是否可以向父亲连边

容易用类似树形背包的方式合并，每次决策儿子是否连接到自己上面

注意：一个长度\(>1\)的段，需要考虑正反方向的排放

复杂度为\(O(\sum k_i^2)\)

Part2 合并每棵树的段

相邻两段不同色，考虑容斥求解

枚举这棵树中的\(i\)个段自己生成了\(j\)个不合法的相邻，\(i\)个段合并生成\(i-j\)个段，且乘上容斥系数\((-1)^j\)

\(i\)个并掉\(j\)个，方案数计算如下：

先把\(i\)个排好，乘上\(i!\)，然后选择\(j\)个间隔合并掉\(\binom{i-1}{j}\)，然后对于剩下的\(i-j\)个元素无序，需要除掉\((i-j)!\)

背包合并容斥之后的结果，对于当前的\(i\)个元素，任意排列即可

然而上面是理想情况，还需要考虑\(1\)号元素不能被排列，要强制最后一个段不是1树的段

这一部分，在树1的容斥以及最终背包合并时特殊处理即可，即少排列一个元素，且最后合并时先选一个放在最后面

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO==‘-‘;
	do s=(s<<1)+(s<<3)+(IO^‘0‘);
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=5e3+10,P=998244353;

int n,m;
int I[N],J[N],C[N][N];
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

struct Edge{
	int to,nxt;
} e[N<<1];
int head[N],ecnt;
void AddEdge(int u,int v){
	e[++ecnt]=(Edge){v,head[u]};
	head[u]=ecnt;
}
int dp[N][N][2]; // 0,1 是否向上连
int G[N][3],H[N][3],sz[N];

void dfs(int u,int f){
	sz[u]=0;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==f) continue;
		dfs(v,u);
	}
	G[0][0]=1,G[0][1]=G[0][2]=0;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==f) continue;
		rep(i,0,sz[u]+sz[v]) rep(j,0,2) H[i][j]=G[i][j],G[i][j]=0;
		rep(i,0,sz[u]) rep(a,0,2) if(H[i][a]) rep(j,0,sz[v]) rep(b,0,min(1,2-a)) G[i+j][a+b]=(G[i+j][a+b]+1ll*H[i][a]*dp[v][j][b])%P;
		sz[u]+=sz[v];
	}
	rep(i,0,sz[u]+1) dp[u][i][0]=dp[u][i][1]=0;
	rep(i,0,sz[u]) {
		dp[u][i+1][0]=(0ll+dp[u][i+1][0]+G[i][0]+2*G[i][1]+2*G[i][2])%P; // 长度>1的段可以翻转
		dp[u][i][1]=(0ll+dp[u][i][1]+G[i][0]+G[i][1])%P; // 如果连了两个儿子，就无法向上连了
	}
	sz[u]++;
}

int F[N],T[N];
void Get(){
	n=rd();
	rep(i,1,n) head[i]=0;
	ecnt=0;
	rep(i,2,n) {
		int u=rd(),v=rd();
		AddEdge(u,v),AddEdge(v,u);
	}
	dfs(1,0);
	rep(i,1,n) {
		F[i]=dp[1][i][0],T[i]=0;
		ll t=1ll*F[i]*J[i]%P;
		rep(j,1,i) {
			T[j]=(T[j]+((i-j)&1?P-1:1)*t%P*C[i-1][i-j]%P*I[j])%P;
		}
	}
}

int S[N],c;

int main(){
	rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
	rep(i,0,N-1) rep(j,C[i][0]=1,i) C[i][j]=C[i-1][j]+C[i-1][j-1],Mod1(C[i][j]);
	m=rd();
	if(m==1) return n=rd(),printf("%d\n",n<=2),0;
	S[0]=1;
	rep(t,1,m-1) {
		Get();
		drep(i,n+c,0) {
			S[i]=0;
			rep(j,1,min(i,n)) S[i]=(S[i]+1ll*S[i-j]*T[j])%P;
		}
		c+=n;
	}
	Get();
	rep(i,1,n) {
		F[i]=dp[1][i][0],T[i]=0;
		ll t=1ll*F[i]*J[i-1]%P; 
		// 特殊处理，不允许排列第一段
		rep(j,1,i) T[j]=(T[j]+((i-j)&1?P-1:1)*t%P*C[i-1][i-j]%P*I[j-1])%P;
	}
	int ans=0;
	// 不允许改变第一段的位置
	// 且强制最后一段不能属于第一棵树
	rep(i,1,c) if(S[i]) rep(j,1,n) if(T[j]) {
		// 强制前面的最后一个在最后
		int t=1ll*J[i]*J[j-1]%P*C[i-1+j-1][j-1]%P;
		ans=(ans+1ll*t*S[i]%P*T[j])%P;
	}
	printf("%d\n",ans);
}

「JSOI2019」神经网络