TopCoder 14084 BearPermutations2【笛卡尔树+dp】

传送：https://vjudge.net/problem/TopCoder-14084

只是利用了笛卡尔树的性质，设f[i][j]为区间[i,j]的贡献，然后枚举中间最大的点k来转移，首先是两侧小区间贡献的，f[i][k-1]*fac[j-k]+f[k+1][j]*fac[k-i]，大概是方案数相乘的形式

然后考虑中间点的儿子的贡献，是\( fac[k-i-1]|*fac[j-k-1]|*sum_{l=i}^{{k-1}\sum_{r=k+1}}{j}r-l \)，前面表示两侧任意排列，后面两个求和可以化简

然后最后整体乘c[j-i][k-i]表示选出一部分作为左儿子

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

class BearPermutations2

{

private:

	long long mod,f[105][105],c[105][105],fac[105];

public:

	long long clc(long long l,long long r)

	{

		return (l+r)*(r-l+1)/2%mod;

	}

	int getSum(int n,int MOD)

	{

		memset(f,0,sizeof(f));

		memset(c,0,sizeof(c));

		mod=MOD;

		fac[0]=1;

		for(int i=1;i<=n;i++)

			fac[i]=fac[i-1]*i%mod;

		c[0][0]=1;

		for(int i=1;i<=n;i++)

		{

			c[i][0]=1;

			for(int j=1;j<=i;j++)

				c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;

		}

		for(int i=n;i>=1;i--)

			for(int j=i;j<=n;j++)

				for(int k=i;k<=j;k++)

				{

					if(k!=i)

						f[i][j]=(f[i][j]+c[j-i][k-i]*f[i][k-1]%mod*fac[j-k]%mod)%mod;

					if(k!=j)

						f[i][j]=(f[i][j]+c[j-i][k-i]*f[k+1][j]%mod*fac[k-i]%mod)%mod;

					if(k!=i&&k!=j)

						f[i][j]=(f[i][j]+c[j-i][k-i]*fac[k-i-1]%mod*fac[j-k-1]%mod*(clc(k+1,j)*(k-i)%mod-clc(i,k-1)*(j-k)%mod+mod)%mod)%mod;

				}

		return (f[1][n]+mod)%mod;

	}

};

巴特西

TopCoder 14084 BearPermutations2【笛卡尔树+dp】

最新文章

热门文章