题目描述

老C的键盘

题解

显然对于每个数 x 都有唯一对应的 \(x/2\) , 然而对于每个数 x 却可以成为 \(x*2\) 和 \(x*2+1\) 的对应数

根据这一特性想到了啥??? 感谢leo101的友情点拨

二叉树!!!

所以可以把 x/2 看做是 x的父亲, 1 显然就是根

可以把 < 看作是由父亲连向儿子的有向边, > 看作是儿子连向父亲的有向边

所以就是求这棵树的拓扑序的方案数就好了!!!

考虑当前节点的两棵子树都已处理完的时候

在满足和当前节点的关系的同时, 两颗子树在拓扑序中出现的顺序显然是没有影响的,所以按照子树大小组合数乱搞就好了

然后设 dp[i][j] 表示 i 号节点在当前子树排在第 j 位的方案数就好了

代码



#include<bits/stdc++.h>

using namespace std;

#define re register

#define ll long long

#define in inline

#define get getchar()

in int read()

{

	int t=0; char ch=get;

	while (ch<'0' || ch>'9') ch=get;

	while (ch<='9' && ch>='0') t=t*10+ch-'0', ch=get;

	return t;

}

const int mod=1e9+7;

const int _=1010;

ll n,dp[_][_],c[_][_],siz[_]; //siz[i]是以i为根的子树节点个数, c[][]是组合数

char s[_];

in void dfs(ll x)

{

	for(re int to=2*x;to<=min(n,2*x+1);to++)

	{

		dfs(to);

		if(s[to]=='>')

		{

			for(re ll k=siz[x]+siz[to]; k>=1; k--)

			{

				ll sum=0;

				for( re int i=1; i<=min(siz[x],k); i++)

				{

					for (re int j=k-i+1;j<=siz[to];j++)

					{

						ll a=(dp[x][i]*dp[to][j])%mod;

						ll b=(c[i-1][k-1]*c[siz[x]-i][siz[x]+siz[to]-k])%mod;

						a=(a*b)%mod;

						sum=(sum+a)%mod;

					}

				}

				dp[x][k]=sum;

			}

		}

		else

		{

			for(re ll k=siz[x]+siz[to]; k>=1; k--)

			{

				ll sum=0;

				for(re int i=1; i<=min(siz[x],k); i++)

					for(re int j=1; j<=min(k-i,siz[to]); j++)

					{

						ll a=(dp[x][i]*dp[to][j])%mod;

						ll b=(c[i-1][k-1]*c[siz[x]-i][siz[x]+siz[to]-k])%mod;

						a=(a*b)%mod;

						sum=(sum+a)%mod;

					}

				dp[x][k]=sum;

			}

		}

		siz[x]+=siz[to]; //子树大小统计

	}

}

int main()

{

	n=read();

	scanf("%s",s+2);

	c[0][0]=1;

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

	{

		c[0][i]=1,c[i][i]=1;

		dp[i][1]=1,siz[i]=1;

		for (re int j=1; j<i; j++) c[j][i]=(c[j][i-1]+c[j-1][i-1])%mod;

	} //预处理组合数

	dfs(1);

	ll ans=0;

	for (re int i=1; i<=n; i++) ans=(ans+dp[1][i])%mod; //因为一号节点是整棵树的根

	cout<<ans<<endl;

	return 0;

}

巴特西

Luogu P3757 [CQOI2017]老C的键盘

题目描述

老C的键盘

题解

二叉树!!!

代码

最新文章

热门文章