题解领域展开后的史山代码

#include<bits/stdc++.h>
#define int long long
#define setp(x) fixed<<setprecision(x)
using namespace std;
constexpr int N=2100;
int n,P,dp[N],g[N],F[N],f[N][N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>P;
	for(int i=0;i<=n;i++)f[i][0]=1;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=(f[i-1][j]+f[i-1][j-1])%P;
	F[0]=F[1]=1;
	for(int i=2;i<=n;i++){
		for(int j=0;j<i;j++){
			(g[i]+=(dp[j]*(i-j)%P*F[i-1-j]%P+dp[i-1-j]*(j+1)%P*F[j]%P+g[j]*F[i-1-j]%P+g[i-j-1]*F[j]%P)%P*f[i-1][j]%P+(F[j]*F[i-1-j]%P*f[i-1][j]%P*(j*(i-j)%P+(j+1)*(i-1-j)%P)%P)%P)%=P;
			(dp[i]+=(dp[j]*F[i-1-j]%P+dp[i-1-j]*F[j]%P+F[j]*F[i-1-j]%P*(i-1)%P)%P*f[i-1][j]%P)%=P;
			(F[i]+=F[j]*F[i-1-j]%P*f[i-1][j]%P)%=P;
		}
	}
	cout<<g[n]<<"\n";
	return 0;
}

比上述代码更加史的代码（本地运行卡退，oirush可以运行）

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=2100;
struct mint{
    int v;
    static int P;
    mint(int x=0):v(x%P){if(v<0)v+=P;}
    static mint qpow(mint A,int B){
        if(B<0) return mint(0);
        mint res(1);
        for(;B;B>>=1,A*=A) if(B&1) res*=A;
        return res;
    }
    static mint qpow(mint A,mint B){return qpow(A,B.v);}
    inline mint& operator+=(const mint& o){v+=o.v;if(v>=P)v-=P;return *this;}
    inline mint& operator-=(const mint& o){v-=o.v;if(v<0)v+=P;return *this;}
    inline mint& operator*=(const mint& o){v=v*o.v%P;return *this;}
    inline mint& operator/=(const mint& o){v=v*qpow(o,P-2).v%P;return *this;}
    friend inline mint operator+(mint a,const mint& b){return a+=b;}
    friend inline mint operator-(mint a,const mint& b){return a-=b;}
    friend inline mint operator*(mint a,const mint& b){return a*=b;}
    friend inline mint operator/(mint a,const mint& b){return a/=b;}
};
int mint::P;
int n;
mint dp[N],g[N],F[N],f[N][N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>mint::P;
	if(mint::P<=1){
		cout<<0<<"\n";
		return 0;
	}
	for(int i=0;i<=n;i++) f[i][0]=1;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=f[i-1][j]+f[i-1][j-1];
	F[0]=F[1]=1;
	for(int i=2;i<=n;i++){
		for(int j=0;j<i;j++){
			g[i]+=(dp[j]*(i-j)*F[i-1-j]+dp[i-1-j]*(j+1)*F[j]+g[j]*F[i-1-j]+g[i-j-1]*F[j])*f[i-1][j]+(F[j]*F[i-1-j]*f[i-1][j]*(j*(i-j)+(j+1)*(i-1-j)));
			dp[i]+=(dp[j]*F[i-1-j]+dp[i-1-j]*F[j]+F[j]*F[i-1-j]*(i-1))*f[i-1][j];
			F[i]+=F[j]*F[i-1-j]*f[i-1][j];
		}
	}
	cout<<g[n].v<<"\n";
	return 0;
}

贴一个完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
#define int long long
int n,mod;
int dp[N][N],c[N][N],fac[N];
int qpow(int a,int b){
	int res=1;
	for(;b;b/=2,a=a*a%mod)if(b&1)res=res*a%mod;
	return res;
}
void init(){
	for(int i=0;i<=n;i++)c[i][i]=c[0][i]=1;
    for(int i=0;i<=n;i++)for(int j=1;j<n;j++)c[j][i]=(c[j-1][i-1]+c[j][i-1])%mod;
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
}
signed main(){
    scanf("%lld%lld",&n,&mod);
    init();
    dp[1][1]=1;for(int i=2;i<=n;i++)for(int j=1;j<=i;j++)dp[i][j]=fac[i-2]*j%mod*(j-1)%mod;
    int ans=0;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=n-i+1;j++){
            ans+=fac[j]*c[j-1][n-i]%mod*j*(n-j)%mod*dp[n-j+1][i];
            ans%=mod;
        }
    }
    printf("%lld\n",ans);
	return 0;
}

P4492

解题思路

提供一个不需要很多组合思想的做法（帮助和我一样的组合蒟蒻）。

设 $dp_i$ 表示节点数为 $i$ 的所有二叉树中每个节点到根距离之和的和，$g_i$ 表示节点数为 $i$ 的所有二叉树中任意两个节点的距离之和的和，$F_i$ 表示节点数为 $i$ 的二叉树的数量。

$F_i=\sum_{j=0}^{i-1}F_j\times F_{i-1-j}\times \dbinom{i}{j}$。

其中 $j$ 表示左子树的节点数，因为有 $i$ 个节点，根肯定是确定的，所以要进行 $i-1$ 次加点，左子树要进行 $j$ 次加点，所以从 $i-1$ 次加点中选择 $j$ 次在左子树上加，方案数为 $\dbinom{i}{j}$，这样得到的方案数是左子树中节点的编号序列和右儿子中节点的编号序列，所以还要乘上 $F_j\times F_{i-1-j}$。

$dp_i=\sum_{j=0}^{i-1}(dp_j\times F_{i-1-j}+dp_{i-1-j}\times F_j+F_j\times F_{i-1-j}\times (i-1))\times \dbinom{i}{j}$。

先分好编号序列，方案数为 $\dbinom{i}{j}$，如果不考虑右子树的情况，那么在所有情况中根到每个左子树中的节点的距离和就是 $dp_j$，一共有 $F_{i-1-j}$ 种，所以左子树的贡献为 $dp_j\times F_{i-1-j}$，右子树同理，还要加上根和左儿子、右儿子连边的贡献，显然在每种情况中两条边的贡献和为 $i-1$。

$g_i=\sum_{j=0}^{i-1}(dp_j\times (i-j)\times F_{i-1-j}+dp_{i-1-j}\times(j+1)\times F_j+g_j\times F_{i-1-j}+g_{i-1-j}\times F_j+F_j\times F_{i-1-j}\times(j\times(i-j)+(i-j-1)\times (j+1)))\dbinom{i}{j}$。

有点长，但不难理解。

先分好编号序列，方案数为 $\dbinom{i}{j}$，先算根和右子树中的节点到每个左子树中的点的路径中左子树上的边的贡献，为 $dp_j\times(i-j)$，因为对于右子树的每种情况都要算一次，所以乘上 $F_{i-1-j}$，根和左子树中的节点到每个右子树中的点的路径中右子树上的边的贡献同理，再计算根和左儿子、右儿子连边的贡献，根和左儿子连边的贡献就是根和右子树中的点到左子树中的点的路径数量，$j\times (i-j)$，根和右儿子连边的贡献同理，每种情况都算一次，乘上 $F_j\times F_{i-1-j}$。

答案就是 $g_n$。

Code：

mint dp[N],g[N],F[N],f[N][N];

int main()
{
	int n;
	scanf("%d%d",&n,&mod);
	rep(i,0,n) f[i][0]=1;
	rep(i,1,n)
		rep(j,1,n)
			f[i][j]=f[i-1][j]+f[i-1][j-1];
	F[1]=F[0]=1;
	rep(i,2,n)
	{
		rep(j,0,i-1)
		{
			g[i]+=(dp[j]*(i-j)*F[i-1-j]+dp[i-1-j]*(j+1)*F[j]+g[j]*F[i-1-j]+g[i-j-1]*F[j])*f[i-1][j];
			g[i]+=F[j]*F[i-1-j]*f[i-1][j]*(j*(i-j)%mod+(j+1)*(i-1-j)%mod);
			dp[i]+=(dp[j]*F[i-1-j]+dp[i-1-j]*F[j]+F[j]*F[i-1-j]*(i-1))*f[i-1][j];
			F[i]+=F[j]*F[i-1-j]*f[i-1][j];
		}
	}
	printf("%d",g[n]);
	return 0;
}