传送门

找规律真挺晕的……我画了两个图全画错了
但不康题解真想不到解法

发现一棵黑色节点为根的子树中每层白色节点个数为斐波那契数
然后题解很神仙的分出了两种情况
当两个点的lca是白色点时，可以枚举距离，则lca的深度范围可知，就可求了
当lca为黑色点时，可以\(n^3\)分别枚举根节点深度，左儿子中白点深度，右儿子中白点深度求解
考虑如何化为\(n^2\)
发现子树都是一样的，每个深度有多少子树可以算出来
所以最外层循环可以优化掉
可以令\(f[i][j]\)为以黑色节点为根时，两个白点深度小于等于\(i\)，距离为\(j\)时的方案数
预处理就枚举左右儿子深度即可
最后最外层循环用斐波那契数优化掉就行
是真的非常难搞，写了巨久，具体见代码

Code:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 10010
#define ll long long 
//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int n;
const ll mod=123456789;
ll fib[N], sum[N], ans[N], f[5010][N], dlt[N];

int main()
{
	n=read();
	fib[1]=fib[2]=1;
	for (int i=3; i<N; ++i) fib[i]=(fib[i-1]+fib[i-2])%mod;
	for (int i=1; i<N; ++i) sum[i]=(sum[i-1]+fib[i])%mod;
	for (int i=1; i<N; ++i) dlt[i]=fib[i]-fib[i-1];
	
	for (int i=1; i<=n; ++i) 
		for (int j=i+2; j<=n; ++j) 
			ans[j-i]+=dlt[i]%mod*fib[j-i-1]%mod, ans[j-i]%=mod;
	#if 0
	for (int i=2; i<=n; ++i) 
		for (int j=i+2; j<=n; ++j) 
			for (int k=i+1; k<=n; ++k) 
				ans[j-i+k-i]+=fib[i-1]*fib[j-i-1]%mod*(fib[k-i]-fib[k-i-1])%mod, ans[j-i+k-i]%=mod; //, cout<<j-i+k-i<<' '<<fib[i-1]*fib[j-i-1]%mod*(fib[k-i]-fib[k-i-1])%mod<<endl;
	#endif
	
	for (int i=2; i<=n; ++i) {
		for (int j=1; j<=2*n; ++j) f[i][j]+=f[i-1][j];
		for (int j=1; j<=n; ++j) 
			f[max(i, j)][i+j]+=fib[i-1]*dlt[j]%mod, f[max(i, j)][i+j]%=mod; //, cout<<i<<' '<<j<<endl;
	}
	
	//for (int i=1; i<=n; ++i) {for (int j=1; j<=2*n; ++j) cout<<f[i][j]<<' '; cout<<endl;}
	
	for (int i=2; i<=n; ++i) 
		for (int j=3; j<=2*n; ++j)
			ans[j]+=fib[i-1]*f[n-i][j], ans[j]%=mod;
	
	for (int i=1; i<=n*2; ++i) printf("%lld ", (ans[i]%mod+mod)%mod);
	printf("\n");
	
	return 0;
}