记录编号	537299	评测结果	AAAAAAAAAA
题目名称	哈密尔顿路	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	1.810 s
提交时间	2019-07-10 23:51:56	内存使用	205.22 MiB

#include<bits/stdc++.h>
#define N 5010
#define mo 1000000007
using namespace std;
int dp1[N][N],n,dp2[N][N],jie[N],j3[N],j2[N];
string s;
int main(){
	freopen("pathh.in","r",stdin);
	freopen("pathh.out","w",stdout);
	cin>>s;
	n=s.length();
	dp1[n+1][0]=1;
	for (int i=n+1;i>=2;i--){
		for (int j=0;j<=n+1-i;j++){
			if (s[i-2]=='<'){
				dp1[i-1][j+1]=(dp1[i-1][j+1]+dp1[i][j])%mo;
				dp1[i-1][j]=(dp1[i-1][j]+1ll*dp1[i][j]*j)%mo;
			}else{
				if (j)dp1[i-1][j-1]=(dp1[i-1][j-1]+1ll*dp1[i][j]*(j-1)*j)%mo;
				dp1[i-1][j]=(dp1[i-1][j]+1ll*dp1[i][j]*j)%mo;
			}
		}
	}
	dp2[0][0]=1;
	for (int i=0;i<=n-1;i++){
		for (int j=0;j<=i;j++){
			if (s[i]=='>'){
				dp2[i+1][j+1]=(dp2[i+1][j+1]+dp2[i][j])%mo;
				dp2[i+1][j]=(dp2[i+1][j]+1ll*dp2[i][j]*j)%mo;
			}else{
				if (j>1)dp2[i+1][j-1]=(dp2[i+1][j-1]+1ll*dp2[i][j]*(j-1)*j)%mo;
				dp2[i+1][j]=(dp2[i+1][j]+1ll*dp2[i][j]*j)%mo;
			}
		}
	}
	jie[0]=1;
	for (int i=1;i<=n;i++) jie[i]=1ll*jie[i-1]*i%mo;
	for (int i=1;i<=n;i++) j3[i]=1ll*jie[i]*jie[i]%mo,j2[i]=1ll*jie[i]*jie[i-1]%mo;
	for (int i=1;i<=n;i++){
		int sum=0;
		for (int j=1;j<=n;j++){
			sum=(sum+(2ll*dp1[i+1][j]*dp2[i-1][j]%mo)*j3[j]+((1ll*dp1[i+1][j]*dp2[i-1][j-1]+1ll*dp2[i-1][j]*dp1[i+1][j-1])%mo)*j2[j])%mo;
		}
		cout<<sum<<' ';
	}
	cout<<endl;
	return 0;          
}