Byteland_Trip

题目传送门
题意:略……

$l[i][j]$表示从左边开始的前$i$个字符组成$j$个向右的半环的方案数.
$r[i][j]$表示从右边开始的前$i$个字符组成$j$个向左的半环的方案数.
然后就可以愉快的转移了……
然后就可以枚举终点愉快的统计答案了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int mod = 1e9 + 7;
const int maxn = 5005;
void add(int &x,int y) {
x += y;
if(x >= mod) x -= mod;
}
int mul(int x,int y) {
LL z = 1LL * x * y;
return z - z / mod * mod;
}
int p[maxn],l[maxn][maxn],r[maxn][maxn];
char s[maxn];
int main(){
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n,i,j;
scanf("%s",s);
n = strlen(s);
for(p[0] = i = 1;i <= n; i++) p[i] = mul(i,p[i - 1]);
if(n == 1) return puts("1");
l[1][1] = (s[0] == '>');
for(i = 1;i < n; i++) {
for(j = 1;j <= i; j++) add(l[i + 1][j],mul(l[i][j],j));
if(s[i] == '<') {
for(j = 2;j <= i; j++) add(l[i + 1][j - 1],mul(l[i][j],mul(j,j - 1)));
} else {
for(j = 1;j <= i; j++) add(l[i + 1][j + 1],l[i][j]);
}
}
reverse(s,s + n);
r[1][1] = (s[0] == '<');
for(i = 1;i < n; i++) {
for(j = 1;j <= i; j++) add(r[i + 1][j],mul(r[i][j],j));
if(s[i] == '>') {
for(j = 2;j <= i; j++) add(r[i + 1][j - 1],mul(r[i][j],mul(j,j - 1)));
} else {
for(j = 1;j <= i; j++) add(r[i + 1][j + 1],r[i][j]);
}
}
for(i = 1;i <= n; i++) {
if(i == 1) printf("%d ",r[n - 1][1]);
else if(i == n) printf("%d ",l[n - 1][1]);
else {
int ans = 0;
for(j = 1;j < i; j++) {
add(ans,mul(mul(mul(l[i - 1][j],r[n - i][j]),mul(p[j],p[j])),2));
add(ans,mul(mul(l[i - 1][j],r[n - i][j + 1]),mul(p[j],p[j + 1])));
add(ans,mul(mul(l[i - 1][j + 1],r[n - i][j]),mul(p[j],p[j + 1])));
}
printf("%d ",ans);
}
}
puts("");
return 0;
}