C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 1364K, 提交时间: 2023-02-17 19:13:17

#include <cstdlib>
# include <iostream>
# include <algorithm>
# include <cstdio>
# include <cmath>
# include <iomanip>
# include <cstring>
# include <queue>
# include <map>
# define LL long long
# define imax(a , b) ( (a) > (b) ? (a) : (b))
# define imin(a , b) ( (a) < (b) ? (a) : (b))
# define rl ro << 1
# define rr ro << 1 | 1
using namespace std;
const LL N = 100 + 511 , oo = 0x3f3f3f3f , M = 1e9 + 7;
char s[N];
LL n , f[N][N] , t[N] ,sz[N] ,c[N][N];
void dfs(LL x)
{
	sz[x] = 1 , f[x][1] = 1;

	for (LL p = 0; p <= 1; ++p)
	{
		LL y = x * 2 + p;
		if (y > n) break;

		dfs(y);

		for (LL i = 0; i <= n; ++i) t[i] = f[x][i] , f[x][i] = 0;

		for (LL i = 1; i <= sz[x]; ++i)
			for (LL j = 1; j <= sz[y]; ++j)
				if (s[y] == '>')
					for (LL k = i + j; k <= i + sz[y]; ++k)
						(f[x][k] += t[i] * f[y][j] % M * c[k - 1][i - 1] % M * c[sz[x] + sz[y] - k][sz[x] - i] % M) %= M;
				else
					for (LL k = i; k < i + j; ++k)
						(f[x][k] += t[i] * f[y][j] % M * c[k - 1][i - 1] % M * c[sz[x] + sz[y] - k][sz[x] - i] % M) %= M;

		sz[x] += sz[y];
	}
}
int main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0) , cout.tie(0);

	cin>>n;
	cin>>s + 2;

	for (LL i = 0; i <= n; ++i)
	{
		c[i][0] = c[i][i] = 1;
		for (LL j = 1; j < i; ++j)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % M;
	}
	dfs(1);
	LL ans = 0;
	for (LL i = 1; i <= n; ++i)
		(ans += f[1][i]) %= M;
	cout<<ans;
}

C++(clang++ 11.0.1) 解法, 执行用时: 5ms, 内存消耗: 2828K, 提交时间: 2022-10-04 17:58:39

#include<bits/stdc++.h>
using namespace std ;
const int N = 505 , mod = 1e9 + 7 ;
#define ll long long
int n ;
char s[N] ;
vector<pair<int,int>> g[N] ;
int siz[N] ;
ll f[N][N],C[N][N],h[N] ;
void init(int n=N-5)
{
	C[0][0]=1 ;
	for(int i=1;i<=n;++i)
	{
		C[i][0]=C[i][i]=1 ;
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod ;
	}
}
void dfs(int x)
{
	f[x][1]=1 ; siz[x]=1 ;
	for(auto &z:g[x])
	{
		int y=z.first ;
		dfs(y) ;
		memcpy(h,f[x],sizeof(h)) ;
		memset(f[x],0,sizeof(f[x])) ;
		if(z.second==1)
		{
			for(int p1=1;p1<=siz[x];++p1)
				for(int p2=1;p2<=siz[y];++p2)
					for(int p3=p1;p3<=p1+p2-1;++p3)
						f[x][p3]=(f[x][p3]+C[p3-1][p1-1]*C[siz[x]+siz[y]-p3][siz[x]-p1]%mod*f[y][p2]%mod*h[p1]%mod)%mod ;
		}
		else
		{
			for(int p1=1;p1<=siz[x];++p1)
				for(int p2=1;p2<=siz[y];++p2)
					for(int p3=p1+p2;p3<=p1+siz[y];++p3)
						f[x][p3]=(f[x][p3]+C[p3-1][p1-1]*C[siz[x]+siz[y]-p3][siz[x]-p1]%mod*f[y][p2]%mod*h[p1]%mod)%mod ;
		}
		siz[x]+=siz[y] ;
	}
}
int main()
{
	scanf("%d%s",&n,s+1) ;
	init() ;
	for(int i=2;i<=n;++i)
		g[i/2].push_back({i,s[i-1]=='<'}) ;
	dfs(1) ;
	ll ans=0 ;
	for(int i=1;i<=n;++i) ans=(ans+f[1][i])%mod ;
	printf("%lld\n",ans) ;
	return 0 ;
}