「GDOI2020模拟赛day1」Permutation

为了便于叙述，设原题中的 $n$ 为$N$

题目分析

要求一个$1-n$的环排列，看成是一个环遍历

发现每条边的权值限制了遍历过程中穿过这条边的次数

取$1$为根，强制从$1$开始遍历，考虑以一个个自由段（即未确定前后连接关系的子段）的形式维护$u$子树中的序列段

那么，只需要满足$u$子树中自由段的个数为$\frac{w(u,fa_u)} {2}$ （每一个自由段的两端均对应一次跨越）即可

分析即可发现$w(u,fa_u)$显然是$O(size_u)$级别的，因此考虑树形背包

那么我们就需要支持合并两组自由段

$O(N^3-N^2\log N)$

设当前$1\ldots n$个自由端，合并上$m$个自由段(从子树合并上来是恰好$m$个)

注意这些自由段之间是无序的

先考虑一个简单的模型：

把$n$个无序自由段拼接成$m$个无序自由段，设方案数为$W(n,m)$，则考虑

先把$n$个自由段排列，然后选出$n-m$个间隔连接，然后除掉得到的$m$个段之间的排列

得到$\begin{aligned} W(n,m)=\frac{n!} {m!}\binom{n-1} {n-m} \end{aligned}$

类似的，可以把$n+m$个自由段排成一排，合并成若干段

但是显然存在的问题就是：可能在两组自由段之间形成了连接，这样的连接是非法的

因此考虑容斥

$\begin{aligned} dp'_{d}\longleftarrow\sum_{i=1}^ndp_{u,i}\sum_{j=1}^idp_v (-1)^{i-j}W(i,j) \sum_{k=1}^m (-1)^{m-k}W(m-1,k)\sum_{d=1}^{j+k}W(j+k,d)\end{aligned}$

将上式分解为四步转移

$n,i\rightarrow j,O(n^2)$

$m\rightarrow k,O(m)$

$j,k\rightarrow j+k,O(nm)$

$j+k\rightarrow d,O((n+m)^2)$

其中$O(n^2,(n+m)^2)$的部分如果用卷积优化，即可做到$O(N^2\log N)$

但是$O(N^3)$就$pts75$了…

Tips:注意在将$1$号节点加入序列时，用上面的方法无法保证它在序列首

需要特殊处理，始终强制它在第一个

$O(N^2)$

当我发现这个做法不需要任何优化就可以做到$O(N^2)$的时候。。。。

把这个容斥的过程爆开

先对于每个儿子的$dp$值按照容斥系数进行上文中$m\rightarrow k$的变换，复杂度为$O(size_u)$

然后进行背包合并，由树形背包的复杂度分析，总复杂度为$O(N^2)$

最后发现其实我们只需要知道$dp_{u,w(u,fa_u)}$，因此这里也只需要$O(size_u)$

综上，复杂度为$O(N^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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)); }

const int DEBUG=1;
#define Log(...) (DEBUG&&(fprintf(stderr,__VA_ARGS__)))

char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

bool Mbe;
const int N=5010;

int n,P;
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;
}
int I[N],J[N],C[N][N],W[N][N];

struct Edge{
	int to,nxt,w;
} e[N<<1];
int head[N],ecnt;
void AddEdge(int u,int v,int w){
	e[++ecnt]=(Edge){v,head[u],w};
	head[u]=ecnt;
}

int sz[N],w[N],dp[N][N],T[N];
int A[N],B[N];

void dfs(int u,int f){
	sz[u]=0,dp[u][0]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==f) continue;
		w[v]=e[i].w,dfs(v,u);
		rep(a,0,sz[u]) T[a]=dp[u][a],dp[u][a]=0;
		rep(a,0,sz[u]) rep(b,1,sz[v]) dp[u][a+b]=(dp[u][a+b]+1ll*T[a]*dp[v][b])%P;
		sz[u]+=sz[v];
	}
	int s=0;
	rep(i,w[u],sz[u]+1) {
		int e=W[i][w[u]];
		if(u==1) e=1ll*C[i-1][i-w[u]]*J[i-1]%P*I[w[u]-1]%P;
		s=(s+1ll*e*dp[u][i-1])%P;
	}
    // 求出我们需要的点值
	
	rep(i,w[u]+1,sz[u]) dp[u][i]=0;
	if(!s) puts("0"),exit(0);
    // 容斥系数变换
	rep(i,1,w[u]) {
		dp[u][i]=1ll*s*W[w[u]][i]%P;
		if((w[u]-i)&1) dp[u][i]=P-dp[u][i];
	}
	sz[u]=w[u];
}

bool Med;
int main(){
	Log("Memory taken %.2lf\n",(&Med-&Mbe)/1024.0/1024.0);
	n=rd(),P=rd();
	rep(i,J[0]=1,n) J[i]=1ll*J[i-1]*i%P;
	I[n]=qpow(J[n]);
	drep(i,n,1) I[i-1]=1ll*I[i]*i%P;
	rep(i,0,n) rep(j,C[i][0]=1,i) C[i][j]=C[i-1][j]+C[i-1][j-1],Mod1(C[i][j]),W[i][j]=1ll*C[i-1][i-j]*J[i]%P*I[j]%P;
	rep(i,2,n){
		int u=rd(),v=rd(),w=rd();
		if(w&1) return puts("0");
		AddEdge(u,v,w/=2),AddEdge(v,u,w);
	}
	dfs(w[1]=1,0);
	dp[1][1]=1ll*dp[1][1]*n%P;
	printf("%d\n",dp[1][1]);
}