[ZJOI2022] 樹(shù) 題解

知識(shí)點(diǎn)

計(jì)數(shù)動(dòng)態(tài)規(guī)劃，容斥。

題意簡(jiǎn)述

要求生成兩棵樹(shù)，滿足一下三個(gè)條件：

在第一棵樹(shù)中：\(1\) 為根，對(duì)于 \(i\in [2,m]\)，從 \([1,i-1]\) 中選一個(gè)點(diǎn)作為它的父節(jié)點(diǎn)。
在第二棵樹(shù)中：\(m\) 為根，對(duì)于 \(i\in [1,m-1]\)，從 \([i+1,m]\) 中選一個(gè)點(diǎn)作為它的父節(jié)點(diǎn)。
對(duì)于 \(i \in [1,m]\)，點(diǎn) \(i\) 不能在兩棵樹(shù)中同時(shí)為葉子結(jié)點(diǎn)。

問(wèn) \(m \in [1,n]\) 時(shí)的方案數(shù)。

分析

\(O(n!n)\)

爆搜即可。

\(O(n^22^n)\)

暴力狀壓即可。

namespace Sub2 {
	constexpr int N(20+10),St((1<<20)+10);
	int cnt[St];
	int f[N][St];

	bool Check() { return n<=20; }

	int Cmain() {
		FOR(i,1,St-5)cnt[i]=cnt[i>>1]+(i&1);
		f[1][1]=1,f[2][2]=1;
		FOR(i,3,n) {
			const int U((1<<(i-1))-1);
			FOR(S,1,U) {
				toadd(f[i][S|1<<(i-1)],mul(f[i-1][S],i-1-cnt[S]));
				FOR(j,1,i-1)if(S&1<<(j-1))toadd(f[i][(S^(1<<(j-1)))|1<<(i-1)],f[i-1][S]);
			}
		}
		static int res[N+10];
		FOR(i,2,n) {
			const int U((1<<i)-1);
			int ans(0);
			FOR(S,0,U)if(f[i][S])toadd(ans,mul(f[i][S],f[i][S]));
			cout<<ans<<endl;
			res[i]=add(ans,Mod-res[i-1]);
		}
		return 0;
	}

}

\(O(n^5)\)

考慮從一個(gè)點(diǎn)慢慢加入時(shí)，合并第一棵樹(shù)和第二棵樹(shù)的狀態(tài)來(lái)計(jì)數(shù)。

第一棵樹(shù)始終都是一棵樹(shù)，但是第二棵樹(shù)在完全成型前就是一堆連通塊，那么我們可以通過(guò)這個(gè)性質(zhì)來(lái)設(shè)計(jì)狀態(tài)：\(f_{i,j,k,q}\) 表示加入第 \(i\) 個(gè)節(jié)點(diǎn)時(shí)，第一棵樹(shù)中有 \(j\) 個(gè)有子節(jié)點(diǎn)的非葉節(jié)點(diǎn)，有 \(k\) 個(gè)無(wú)子節(jié)點(diǎn)的非葉節(jié)點(diǎn)，而第二棵樹(shù)有 \(q\) 個(gè)連通塊的數(shù)量。

邊界：\(f_{1,0,1,1} = 1\)。

轉(zhuǎn)移方程：

加入葉子結(jié)點(diǎn)（第一棵樹(shù)中，下同）：（\(\to\) 代表加到，下同）

\[\forall p \in [1,q],j {q\choose q-p+1} f_{i,j,k,q} \to f_{i+1,j,k,p} \\ \forall p \in [1,q],k>1,k {q\choose q-p+1} f_{i,j,k,q} \to f_{i+1,j+1,k-1,p} \\ \]
加入非葉節(jié)點(diǎn)：

\[jf_{i,j,k,q} \to f_{i+1,j,k+1,q+1} \\ kf_{i,j,k,q} \to f_{i+1,j+1,k,q+1} \\ \]

統(tǒng)計(jì)答案：對(duì)于 \(i\)，答案為 \(\sum_{j=1}^{i-1} f_{i,j,0,1}\)。

namespace Sub3 {
	constexpr int N(100+10);
	int f[2][N][N][N];
	int (*F)[N][N](f[0]),(*G)[N][N](f[1]);

	bool Check() { return n<=50; }

	int Cmain() {
		F[0][1][1]=1;
		FOR(i,1,n-1) {
			FOR(j,1,i+1)FOR(k,0,i+1-j)FOR(q,1,i+1)G[j][k][q]=0;
			FOR(j,i>1,i-1)FOR(k,0,i-j)FOR(q,1,i)if(F[j][k][q]) {
				FOR(p,1,q)toadd(G[j][k][p],mul(j,C[q][q-p+1],F[j][k][q]));
				if(k)FOR(p,1,q)toadd(G[j+1][k-1][p],mul(k,C[q][q-p+1],F[j][k][q]));
				toadd(G[j][k+1][q+1],mul(j,F[j][k][q])),toadd(G[j+1][k][q+1],mul(k,F[j][k][q]));
			}
			int ans(0);
			FOR(j,1,i)toadd(ans,G[j][0][1]);
			cout<<ans<<endl,swap(F,G);
		}
		return 0;
	}

}

\(O(n^4)\)

考慮優(yōu)化上述算法，我們發(fā)現(xiàn)看起來(lái)最可優(yōu)化的似乎是 \(p\) 的枚舉。

那我們可以嘗試在加入連通塊時(shí)就給它分組，確定一組中之后都連同一個(gè)父節(jié)點(diǎn)，那么這時(shí)轉(zhuǎn)移復(fù)雜度就減小到 \(O(1)\) 了。

\(f_{i,j,k,q}\) 表示加入第 \(i\) 個(gè)節(jié)點(diǎn)時(shí)，第一棵樹(shù)中有 \(j\) 個(gè)有子節(jié)點(diǎn)的非葉節(jié)點(diǎn)，有 \(k\) 個(gè)無(wú)子節(jié)點(diǎn)的非葉節(jié)點(diǎn)，而第二棵樹(shù)有 \(q\) 組連通塊的數(shù)量。

邊界：\(f_{1,0,1,1} = 1\)。

轉(zhuǎn)移方程：

加入葉子結(jié)點(diǎn)：

\[q(q-1)j f_{i,j,k,q} \to f_{i+1,j,k,q-1} [q > 1]\\ qj f_{i,j,k,q} \to f_{i+1,j,k,q} \\ q(q-1)k f_{i,j,k,q} \to f_{i+1,j+1,k-1,q-1} [q > 1]\\ qk f_{i,j,k,q} \to f_{i+1,j+1,k-1,q} \\ \]
加入非葉節(jié)點(diǎn)：

\[qjf_{i,j,k,q} \to f_{i+1,j,k+1,q} \\ jf_{i,j,k,q} \to f_{i+1,j,k+1,q+1} \\ qkf_{i,j,k,q} \to f_{i+1,j+1,k,q} \\ kf_{i,j,k,q} \to f_{i+1,j+1,k,q+1} \\ \]

統(tǒng)計(jì)答案：這種狀態(tài)似乎不是很好統(tǒng)計(jì)，因?yàn)槲覀儫o(wú)法判斷第二棵樹(shù)是否成型，那么我們?cè)诮y(tǒng)計(jì) \(i\) 的時(shí)候要跑到 \(i-1\) 的時(shí)候模擬讓它重新生成一遍，即 \(\sum_{j=1}^{i-1} (j f_{i-1,j,0,1} + f_{i-1,j-1,1,1})\)。

namespace Sub4 {
	using Sub3::f;
	using Sub3::F;
	using Sub3::G;

	bool Check() { return n<=100; }

	int Cmain() {
		F[0][1][1]=1;
		FOR(i,1,n-1) {
			FOR(j,0,i+1)FOR(k,0,i+1-j)FOR(q,1,i+1)G[j][k][q]=0;
			FOR(j,i>1,i-1)FOR(k,0,i-j)FOR(q,1,i)if(F[j][k][q]) {
				if(q>1)toadd(G[j][k][q-1],mul(q,q-1,j,F[j][k][q]));
				toadd(G[j][k][q],mul(q,j,F[j][k][q]));
				if(q>1)toadd(G[j+1][k-1][q-1],mul(q,q-1,k,F[j][k][q]));
				toadd(G[j+1][k-1][q],mul(q,k,F[j][k][q]));
				toadd(G[j][k+1][q],mul(q,j,F[j][k][q]));
				toadd(G[j][k+1][q+1],mul(j,F[j][k][q]));
				toadd(G[j+1][k][q],mul(q,k,F[j][k][q]));
				toadd(G[j+1][k][q+1],mul(k,F[j][k][q]));
			}
			int ans(0);
			FOR(j,1,i)toadd(ans,mul(j,F[j][0][1]),F[j-1][1][1]);
			cout<<ans<<endl,swap(F,G);
		}
		return 0;
	}

}

\(O(n^3)\)

法一

接下來(lái)要優(yōu)化的肯定是 \(j,k\) 兩維，我們可以簡(jiǎn)化它們：

\(f_{i,j,k}\) 表示加入第 \(i\) 個(gè)節(jié)點(diǎn)時(shí)，第一棵樹(shù)中包含 \([1,i]\) 的子圖有 \(j\) 個(gè)非葉結(jié)點(diǎn)——即包含 \([i+1,n]\) 的子圖中有 \(j\) 組連通塊——而第二棵樹(shù)中包含 \([1,i]\) 的子圖有 \(k\) 組連通塊——即 \([i+1,n]\) 中有 \(k\) 個(gè)非葉結(jié)點(diǎn)——時(shí)的數(shù)量。這個(gè)時(shí)候轉(zhuǎn)移需要帶一點(diǎn)容斥。

邊界：\(\forall i \in [1,n],f_{1,2,i} = i\)，表示點(diǎn)在 \(i\) 組連通塊中選擇的方案數(shù)。

轉(zhuǎn)移方程：

加入葉子結(jié)點(diǎn)：（\(\gets\) 表示加到，下同）

\[f_{i,j,k} \gets jkf_{i-1,j,k+1} - jkf_{i-1,j,k} \\ \]
前者是第一棵樹(shù)中為葉子，第二棵樹(shù)為非葉子的總方案數(shù)，后者是容斥掉的不合法方案數(shù)：代表了在第二棵樹(shù)看似為非葉子，但其實(shí)并沒(méi)有子節(jié)點(diǎn)的方案數(shù)。
加入非葉節(jié)點(diǎn)：

\[f_{i,j,k} \gets (j-1)kf_{i-1,j-1,k} - jkf_{i-1,j,k} \\ \]
同理。

（這部分如果轉(zhuǎn)換成刷表來(lái)做會(huì)更快。）

統(tǒng)計(jì)答案：\(ans_2 = 1,ans_i = \sum_{j=1}^i jf_{j,1}\)。

namespace Sub {
	int f[2][N][N];
	int (*F)[N](f[0]),(*G)[N](f[1]);

	int Cmain() {
		FOR(i,1,n)F[1][i]=i;
		cout<<"1"<<endl;
		FOR(i,3,n) {
			FOR(j,1,i)FOR(k,1,n)G[j][k]=mul(
				k,add(
					mul(
						j,
						add(F[j][k+1],Mod-F[j][k],F[j-1][k],Mod-F[j][k])
					),
					Mod-F[j-1][k]
				)
			);
			int ans(0);
			FOR(j,1,i)toadd(ans,mul(j,G[j][1]));
			cout<<ans<<endl,swap(F,G);
		}
		return 0;
	}

}

法二

我們直接從狀壓的部分跳過(guò)來(lái)，嘗試大力容斥。

定義：

集合狀態(tài) \(S\) 表示在一棵樹(shù)中，對(duì)于 \(\forall x \in S\)，\(x\) 都是非葉結(jié)點(diǎn)，其余則是葉節(jié)點(diǎn)。
集合狀態(tài) \(rev_{n}(S)\) 表示將 \(S\) 倒轉(zhuǎn)過(guò)來(lái)，即在一棵樹(shù)中，對(duì)于 \(\forall x \in S\)，\(n-x+1\) 都是非葉結(jié)點(diǎn)，其余則是葉節(jié)點(diǎn)。
集合 \(U_n = [1,n]\cap \mathbb{N}\)。

我們用 \(f(S)\) 表示第一棵樹(shù)上狀態(tài)恰好為 \(S\) 時(shí)，方案數(shù)為多少。那么從狀壓的部分就有：

\[ans_n = \sum_{S \in U_n} f(S)f(rev_n(\complement_{U_n}S)) \]

但考試的時(shí)候打錯(cuò)了，然后偶然發(fā)現(xiàn) \(f(S)=f(rev_n(\complement_{U_n}S))\)，有：

\[ans_n = \sum_{S\in U_n}f^2(S) \]

設(shè) \(g(S)\) 表示第一棵樹(shù)上非葉結(jié)點(diǎn)只屬于 \(S\) 的方案數(shù)，且需保證 \(1 \in S\)，則有：

\[g(S) = \prod_{i=2}^n\sum_{j\in S} [j<i] \]

實(shí)際意義就是第 \(i\) 個(gè)點(diǎn)能取到的父節(jié)點(diǎn)數(shù)量的乘積。那么我們也可以表示出 \(f(S)\) 了：

\[\begin{aligned} f(S) & = \sum_{T \subset S , 1 \notin T} (-1)^{|T|} g(S \setminus T) \\ f(S) & = \sum_{T \subset S , 1 \notin T} (-1)^{|T|} (\prod_{i=2}^n\sum_{j\in S \setminus T} [j<i])\\ \end{aligned} \]

那我們現(xiàn)在簡(jiǎn)單化一下答案式：

\[\begin{aligned} ans_n & = \sum_{S\in U_n} f^2(S) \\ & = \sum_{S\in U_n} \sum_{T_1 \subset S , 1 \notin T_1} \sum_{T_2 \subset S , 1 \notin T_2} (-1)^{|T_1|+|T_2|} (\prod_{i=2}^n\sum_{j\in S \setminus T_1} [j<i]) (\prod_{i=2}^n\sum_{j\in S \setminus T_1} [j<i]) \\ & = \sum_{S\in U_n} \sum_{T_1 \subset S , 1 \notin T_1} \sum_{T_2 \subset S , 1 \notin T_2} (-1)^{|T_1|+|T_2|} \prod_{i=2}^n(\sum_{j\in S \setminus T_2} [j<i]) (\sum_{j\in S \setminus T_2} [j<i]) \\ \end{aligned} \]

那么我們可以開(kāi)始設(shè)計(jì) DP 了。\(f_{i,j,k}\) 表示選了前 \(i\) 個(gè)點(diǎn)，且滿足 \(|S \setminus T_1| = j, |S \setminus T_2| = k\) 時(shí)下式的值：

\[\sum_{S\in U_i} \sum_{T_1 \subset S , 1 \notin T_1} \sum_{T_2 \subset S , 1 \notin T_2} (-1)^{|T_1|+|T_2|} \prod_{x=2}^i(\sum_{y\in S \setminus T_2} [y<x]) (\sum_{y\in S \setminus T_2} [y<x]) \\ \]

邊界：\(f_{1,1,1}=1\)。

轉(zhuǎn)移方程：按順序決策是否要選第 \(i\) 個(gè)點(diǎn)，并且中途要枚舉 \(j,k\)。

\(i \notin S\)：那么必定有 \(i \notin T_1,j \notin T_2\)，即

\[jkf_{i,j,k} \to f_{i,j,k} \\ \]
\(i \in S\)：那么要分四種情況
1. \(i \notin T_1,j \notin T_2\)：
  
  \[jkf_{i,j,k} \to f_{i,j+1,k+1} \\ \]
2. \(i \notin T_1,j \in T_2\)：
  
  \[-jkf_{i,j,k} \to f_{i,j+1,k} \\ \]
3. \(i \in T_1,j \notin T_2\)：
  
  \[-jkf_{i,j,k} \to f_{i,j,k+1} \\ \]
4. \(i \in T_1,j \in T_2\)：
  
  \[jkf_{i,j,k} \to f_{i,j,k} \\ \]

統(tǒng)計(jì)答案：\(ans_i = \sum_{j=1}^i \sum_{k=1}^i f_{i,j,k}\)。

namespace Sub_ {
	using Sub::f;
	using Sub::F;
	using Sub::G;

	int Cmain() {
		F[1][1]=1;
		FOR(i,2,n) {
			FOR(j,1,i)FOR(k,1,i)G[j][k]=0;
			FOR(j,1,i-1)FOR(k,1,i-1)if(F[j][k]) {
				const int val(mul(j*k,F[j][k]));
				/*0*/
				toadd(G[j][k],val);
				/*1*/
				toadd(G[j+1][k+1],val);
				toadd(G[j][k+1],Mod-val);
				toadd(G[j+1][k],Mod-val);
				toadd(G[j][k],val);
			}
			int ans(0);
			FOR(j,1,i)FOR(k,1,i)toadd(ans,G[j][k]);
			cout<<ans<<endl,swap(F,G);
		}
		return 0;
	}

}

完整代碼

#define Plus_Cat "tree"
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define FOR(i,a,b) for(int i(a); i<=(int)(b); ++i)
#define DOR(i,a,b) for(int i(a); i>=(int)(b); --i)
#define EDGE(g,i,x,y) for(int i(g.h[x]),y(g[i].v); ~i; y=g[i=g[i].nxt].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(5e2+10);

#define DE(...) E(#__VA_ARGS__,__VA_ARGS__)
struct Ecat {

	template<class T,class...Types>void operator ()(const char *fmt,const T a) {
		return cerr<<fmt<<":"<<a<<".\n",void();
	}

	template<class T,class...Types>void operator ()(const char *fmt,const T a,const Types...args) {
		while(*fmt^',')cerr<<*fmt++;
		return cerr<<":"<<a<<", ",(*this)(++fmt,args...);
	}

} E;

namespace Modular {
	int Mod;
	int C[N<<1][N<<1];

	template<class T1,class T2>constexpr auto add(const T1 a,const T2 b) {
		return a+b>=Mod?a+b-Mod:a+b;
	}

	template<class T1,class T2>constexpr auto mul(const T1 a,const T2 b) {
		return (ll)a*b%Mod;
	}

	template<class T,class...Types>constexpr auto add(const T a,const Types...args) {
		return add(a,add(args...));
	}

	template<class T,class...Types>constexpr auto mul(const T a,const Types...args) {
		return mul(a,mul(args...));
	}

	template<class T1,class T2>T1 &toadd(T1 &a,const T2 b) {
		return a=add(a,b);
	}

	template<class T1,class T2>T1 &tomul(T1 &a,const T2 b) {
		return a=mul(a,b);
	}

	template<class T0,class T,class...Types>T0 &toadd(T0 &a,const T b,const Types...args) {
		return toadd(a,b),toadd(a,args...);
	}

	template<class T0,class T,class...Types>T0 &tomul(T0 &a,const T b,const Types...args) {
		return tomul(a,b),tomul(a,args...);
	}

	void Init(int n=(N<<1)-5) {
		FOR(i,0,n) {
			C[i][0]=1;
			FOR(j,1,i)C[i][j]=add(C[i-1][j-1],C[i-1][j]);
		}
	}

} using namespace Modular;

int n;

namespace Sub2 {
	constexpr int N(20+10),St((1<<20)+10);
	int cnt[St];
	int f[N][St];

	bool Check() { return n<=20; }

	int Cmain() {
		FOR(i,1,St-5)cnt[i]=cnt[i>>1]+(i&1);
		f[1][1]=1,f[2][2]=1;
		FOR(i,3,n) {
			const int U((1<<(i-1))-1);
			FOR(S,1,U) {
				toadd(f[i][S|1<<(i-1)],mul(f[i-1][S],i-1-cnt[S]));
				FOR(j,1,i-1)if(S&1<<(j-1))toadd(f[i][(S^(1<<(j-1)))|1<<(i-1)],f[i-1][S]);
			}
		}
		static int res[N+10];
		FOR(i,2,n) {
			const int U((1<<i)-1);
			int ans(0);
			FOR(S,0,U)if(f[i][S])toadd(ans,mul(f[i][S],f[i][S]));
			cout<<ans<<endl;
			res[i]=add(ans,Mod-res[i-1]);
		}
		return 0;
	}

}

namespace Sub3 {
	constexpr int N(100+10);
	int f[2][N][N][N];
	int (*F)[N][N](f[0]),(*G)[N][N](f[1]);

	bool Check() { return n<=50; }

	int Cmain() {
		F[0][1][1]=1;
		FOR(i,1,n-1) {
			FOR(j,1,i+1)FOR(k,0,i+1-j)FOR(q,1,i+1)G[j][k][q]=0;
			FOR(j,i>1,i-1)FOR(k,0,i-j)FOR(q,1,i)if(F[j][k][q]) {
				FOR(p,1,q)toadd(G[j][k][p],mul(j,C[q][q-p+1],F[j][k][q]));
				if(k)FOR(p,1,q)toadd(G[j+1][k-1][p],mul(k,C[q][q-p+1],F[j][k][q]));
				toadd(G[j][k+1][q+1],mul(j,F[j][k][q])),toadd(G[j+1][k][q+1],mul(k,F[j][k][q]));
			}
			int ans(0);
			FOR(j,1,i)toadd(ans,G[j][0][1]);
			cout<<ans<<endl,swap(F,G);
		}
		return 0;
	}

}

namespace Sub4 {
	using Sub3::f;
	using Sub3::F;
	using Sub3::G;

	bool Check() { return n<=100; }

	int Cmain() {
		F[0][1][1]=1;
		FOR(i,1,n-1) {
			FOR(j,0,i+1)FOR(k,0,i+1-j)FOR(q,1,i+1)G[j][k][q]=0;
			FOR(j,i>1,i-1)FOR(k,0,i-j)FOR(q,1,i)if(F[j][k][q]) {
				if(q>1)toadd(G[j][k][q-1],mul(q,q-1,j,F[j][k][q]));
				toadd(G[j][k][q],mul(q,j,F[j][k][q]));
				if(q>1)toadd(G[j+1][k-1][q-1],mul(q,q-1,k,F[j][k][q]));
				toadd(G[j+1][k-1][q],mul(q,k,F[j][k][q]));
				toadd(G[j][k+1][q],mul(q,j,F[j][k][q]));
				toadd(G[j][k+1][q+1],mul(j,F[j][k][q]));
				toadd(G[j+1][k][q],mul(q,k,F[j][k][q]));
				toadd(G[j+1][k][q+1],mul(k,F[j][k][q]));
			}
			int ans(0);
			FOR(j,1,i)toadd(ans,mul(j,F[j][0][1]),F[j-1][1][1]);
			cout<<ans<<endl,swap(F,G);
		}
		return 0;
	}

}

namespace Sub {
	int f[2][N][N];
	int (*F)[N](f[0]),(*G)[N](f[1]);

	int Cmain() {
		FOR(i,1,n)F[1][i]=i;
		cout<<"1"<<endl;
		FOR(i,3,n) {
			FOR(j,1,i)FOR(k,1,n)G[j][k]=mul(
				k,add(
					mul(
						j,
						add(F[j][k+1],Mod-F[j][k],F[j-1][k],Mod-F[j][k])
					),
					Mod-F[j-1][k]
				)
			);
			int ans(0);
			FOR(j,1,i)toadd(ans,mul(j,G[j][1]));
			cout<<ans<<endl,swap(F,G);
		}
		return 0;
	}

}

namespace Sub_ {
	using Sub::f;
	using Sub::F;
	using Sub::G;

	int Cmain() {
		F[1][1]=1;
		FOR(i,2,n) {
			FOR(j,1,i)FOR(k,1,i)G[j][k]=0;
			FOR(j,1,i-1)FOR(k,1,i-1)if(F[j][k]) {
				const int val(mul(j*k,F[j][k]));
				/*0*/
				toadd(G[j][k],val);
				/*1*/
				toadd(G[j+1][k+1],val);
				toadd(G[j][k+1],Mod-val);
				toadd(G[j+1][k],Mod-val);
				toadd(G[j][k],val);
			}
			int ans(0);
			FOR(j,1,i)FOR(k,1,i)toadd(ans,G[j][k]);
			cout<<ans<<endl,swap(F,G);
		}
		return 0;
	}

}

int main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	cin>>n>>Mod,Init();
	if(Sub2::Check())return Sub2::Cmain();
	if(Sub3::Check())return Sub3::Cmain();
	if(Sub4::Check())return Sub4::Cmain();
	return Sub_::Cmain();
}

posted @ 2025-03-13 21:11 Add_Catalyst 閱讀(15) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

珈貓的小窩

歡迎來(lái)到珈貓的小窩

[ZJOI2022] 樹(shù) 題解

[ZJOI2022] 樹(shù) 題解

知識(shí)點(diǎn)

題意簡(jiǎn)述

分析

\(O(n!n)\)

\(O(n^22^n)\)

\(O(n^5)\)

\(O(n^4)\)

\(O(n^3)\)

法一

法二

完整代碼

公告