Codeforces #722 Div1 : E. Mashtali and Hagh Trees

ありそうで意外にない問題。
https://codeforces.com/contest/1528/problem/E

問題

正整数Nが与えられる。
以下を満たすラベルなし有向グラフは何通りか。

• 最長パスの長さはNである。
• 各点の次数は、(向きを無視して)3以下である。
• 2頂点のペアに対し、片方から片方に辺をたどって遷移できる。もしくはそうでないないなら、両点から遷移可能な点がある。

解法

最後の条件より、このグラフは

• rootから葉の方向に辺の向きが向くような木
• 逆に、葉からrootに対し向きが向くような木

をrootでくっ付けたような形をとる。

そこでまず前者を考える。

dp(n) := rootから葉までの最長パスの長さがnで、rootの次数が2以下であるグラフの個数
dp2(n) := rootから葉までの最長パスの長さがnで、rootの次数がちょうど2であるグラフの個数
sum(n) := dp(1)+dp(2)+....+dp(n)

この時、dp(n) = dp(n-1) + dp(n-1)*sum(n-2) + dp(n-1)*(dp(n-1)+1)/2 である。
+で区切られた2つの項は、以下3通りの和である。

• rootから1つだけdp(n-1)に相当する木のrootに辺を張る場合
• rootからdp(n-1)に相当する木のrootと、sum(n-2)に相当する木に計2本辺を張る場合
• rootからdp(n-1)に相当する2つの木のrootに計2本辺を張る場合

また、dp2(n) = dp(n) - dp(n-1) である。

ここから解を求める。

• 2つの木をくっ付けるケース
  • rootの前と後どちらかが2点隣接することを考えると、2*dp(i)*dp2(N-i-1)の総和となる。
• 1つの木からなるケース
  • rootから1～3個の辺が出るケースを考えると、2*(dp(N)+dp(N-1)*sum(N-2)*(sum(N-2)-1)/2+dp(N-1)*(dp(N-1)+1)/2*sum(N-2) + dp(N-1)*(dp(N-1)+1)*dp(N-2)/6)-1である。
  • -1しているのは、単一パスからなるケースを二重カウントしないためである。

int N;

const int mo=998244353;
ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


ll F[1210101]; //single and double
ll F2[1210101]; //double
ll FS[1210101];
ll F2S[1210101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<ll> FF(1<<21);

	F[0]=F2[0]=FS[0]=F2S[0]=1;
	F[1]=2;
	F2[1]=1;
	FS[1]=3;
	F2S[1]=2;
	for(i=2;i<=N;i++) {
		F[i]=F[i-1]; // single
		F[i]+=F[i-1]; // same
		F[i]+=F[i-1]*(F[i-1]-1)/2; // dif
		F[i]+=F[i-1]*FS[i-2]; // dif
		F[i]%=mo;
		F2[i]=(F[i]+mo-F[i-1])%mo;
		(FS[i]=FS[i-1]+F[i])%=mo;
		(F2S[i]=F2S[i-1]+F2[i])%=mo;
		
	}
	
	ll ret=0;
	
	FOR(i,N) (ret+=F2[i]*F2S[N-1-i])%=mo;
	
	ll pat=0;
	pat=F2[N];
	// triple F[n]1*F[n]1*F[n]1
	pat+=F[N-1];
	// triple F[n]1*F[n]1*F[n]2
	(pat+=F[N-1]*(F[N-1]-1))%=mo;
	// triple F[n]1*F[n]2*F[n]3
	(pat+=F[N-1]*(F[N-1]-1)%mo*(F[N-1]-2)%mo*modpow(6))%=mo;
	// triple F[n]1*F[n]1*FS[n]1
	(pat+=F[N-1]*FS[N-2])%=mo;
	// triple F[n]1*F[n]2*FS[n]1
	(pat+=F[N-1]*(F[N-1]-1)%mo*FS[N-2]%mo*modpow(2))%=mo;
	// triple F[n]1*FS[n]1*FS[n]1
	(pat+=F[N-1]*FS[N-2])%=mo;
	// triple F[n]1*FS[n]1*FS[n]1
	(pat+=F[N-1]*FS[N-2]%mo*(FS[N-2]-1)%mo*modpow(2))%=mo;
	
	
	cout<<(ret+2*pat)%mo<<endl;
	
	
	
}

まとめ

言われてみると難しくないんだけど、これをさっと計算するのはしんどい。