自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 21:52:23，当前版本为作者最后更新于2018-02-24 21:48:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

哇塞！我可以说这是双倍经验吗？

和P4099HEOI2014SAO是重题，而且弱化了!!!

我也是不想说啥了……明明有O(n^2)的复杂度啊……

我可以贴一发我的题解链接嘛……

https://www.luogu.org/blog/ShadowassIIXVIIIIV/solution-p4099

那么我们发现对比HEOI2014来讲，这道题唯一的问题是，没有树QAQ

但是如果你对二叉树的表示相当熟练的话，我们会发现，其实线段树什么的啊，二叉堆什么的啊，都是用2*i，2*i+1来表示父子关系的i/2就是i的父亲，所以树什么的是可以建出来的，还是一只完全二叉树，

如果我们把它的拓扑序排名作为全排列里的位置，那么一个拓扑序一一对应一个全排列

所以是给定二叉树型图，求所有合法拓扑序方案，还只要求O(N^3)算法！

还有就是这道题连小于大于号都给你了……，你甚至不必改HEOI那道题的代码

当然我就只写O(N^3)的代码咯~，毕竟前缀和啥的还得再维护，多麻烦，出题人不为难你就不写了啊，写O(N^2)的去交4099

但是还有一个至关重要的麻烦，转移方程里，要求4个1e9乘一起，显然爆longlong…… 所以分开乘，膜3遍即可

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
ll mod=1e9+7;const int N=110;
ll dp[N][N];ll c[N][N];
ll siz[N];int n;ll res;
char mde[N];
inline void dfs(int x)
{
	for(int v=2*x;v<=min(n,2*x+1);v++)
	{
		dfs(v);
		if(mde[v]=='>')//O(N^3)因为我懒得打前缀和
		{
			for(int k=siz[x]+siz[v];k>=1;k--)//枚举排名
			{
				ll sum=0;
				for(int i=1;i<=min(siz[x],(ll)k);i++)//保证合法性的区间
				{
					for(int j=k-i+1;j<=siz[v];j++)//保证合法性
					{
						ll a=(dp[x][i]*dp[v][j])%mod;ll b=(c[i-1][k-1]*c[siz[x]-i][siz[x]+siz[v]-k])%mod;
						a=(a*b)%mod;sum=(sum+a)%mod;//两个序列的可能取值情况*x前序列组合*x后序列组合
					}
				}
				dp[x][k]=sum;
			}
		}
		else//同上,只是枚举区间变了,转移方程是一样的
		{
			for(int k=siz[x]+siz[v];k>=1;k--)
			{
				ll sum=0;
				for(int i=1;i<=min(siz[x],(ll)k);i++)
				{
					for(int j=1;j<=min((ll)k-i,siz[v]);j++)
					{
						ll a=(dp[x][i]*dp[v][j])%mod;ll b=(c[i-1][k-1]*c[siz[x]-i][siz[x]+siz[v]-k])%mod;
						a=(a*b)%mod;sum=(sum+a)%mod;
					}
				}
				dp[x][k]=sum;
			}
		}
		siz[x]+=siz[v];//别忘了siz
	}
}
int main()
{
	scanf("%d",&n);
	c[0][0]=1;//打表组合数备用
	for(int i=1;i<=n;i++)
	{
		c[0][i]=1;c[i][i]=1;
		for(int j=1;j<i;j++){c[j][i]=(c[j][i-1]+c[j-1][i-1])%mod;}
	}
	scanf("%s",mde+2);//注意从2开始
	for(int i=1;i<=n;i++){dp[i][1]=1;siz[i]=1;}//初始化
	dfs(1);
	for(int i=1;i<=n;i++){res=(res+dp[1][i])%mod;}
	printf("%lld",res);return 0;//拜拜程序~
}