【2017NEERC Moscow Subregional】Byteland Trip 题解

题目大意

  $n$ 个点排成一排，每个点如果为 “<” 则表示可以跳到它左边的一个位置，如果为 “>” 则表示可以跳到它右边的一个位置。
  对每个点 $i$，求以 $i$ 为终点、经过每个点恰好一次的路径数。
  $n \leq 5000$

$$\\$$ $$\\$$ $$\\$$

题解

  对于到达点 $i$ 的每一条路，有时在左边有时在右边，不好处理，我们应该想办法使左右两边分别处理然后合并。
  dp，设 $f_{i,j}$ 表示从左到右做到第 $i$ 个点、形成了 $j$ 个连通块（每个连通块是一段路径，并且最终指向右边）的方案数，再设 $g_{i,j}$ 表示从右到左做到第 $i$ 个点、形成了 $j$ 个连通块（每个连通块最终指向左边）的方案数。
  对于点 $i$，枚举 $j$ 将 $f_{i-1}$ 与 $g_{i+1}$ 合并即是答案。
  求这两个 dp 数组很简单，比如求 $f_i$，第 $i$ 个点如果是 “<”，则要么成为某个连通块的开始，要么连接两个连通块；如果是 “>”，则要么成为某个连通块的末尾，要么新建一个连通块。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=5010;
const LL mo=1e9+7;

int n;
char S[maxn];

LL f[maxn][maxn],g[maxn][maxn],fac[maxn];
int main()
{
	fac[0]=1;
	fo(i,1,5005) fac[i]=fac[i-1]*i%mo;
	
	scanf("%s",S+1);
	n=strlen(S+1);
	if (n==1) {printf("1\n"); return 0;}
	
	f[0][0]=1;
	fo(i,1,n)
		fo(j,1,i)
			if (S[i]=='<') f[i][j]=(f[i-1][j]*j+f[i-1][j+1]*(j+1)%mo*j)%mo;
				else f[i][j]=(f[i-1][j-1]+f[i-1][j]*j)%mo;
	g[n+1][0]=1;
	fd(i,n,1)
		fo(j,1,n-i+1)
			if (S[i]=='<') g[i][j]=(g[i+1][j]*j+g[i+1][j-1])%mo;
				else g[i][j]=(g[i+1][j]*j+g[i+1][j+1]*(j+1)%mo*j)%mo;
	
	fo(i,1,n)
	{
		LL ans=0;
		fo(j,0,i-1)
		{
			if (j) (ans+=fac[j]*fac[j-1]%mo*f[i-1][j]%mo*g[i+1][j-1])%=mo;
			(ans+=fac[j]*fac[j]%mo*2%mo*f[i-1][j]%mo*g[i+1][j])%=mo;
			(ans+=fac[j]*fac[j+1]%mo*f[i-1][j]%mo*g[i+1][j+1])%=mo;
		}
		printf("%I64d ",ans);
	}
}