老C的键盘题解
和这一道几乎一模一样,
代码:
#include<bits/stdc++.h>
#define ll long long
#define lc (x<<1)
#define rc (x<<1|1)
using namespace std;
const int N=106;
const ll mod=1e9+7;
int n,cnt=0,siz[N],head[N];
ll f[N][N],sum[N][N],c[N][N],tmp[N];
char s[N];
struct edge{int nxt,to;}e[N];
inline void add(int u,int v){e[++cnt].nxt=head[u],e[cnt].to=v,head[u]=cnt;}
inline int read(){
int T=0,F=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') F=-1; ch=getchar();}
while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();
return F*T;
}
void build(int l,int r,int x){
if(l==r) return;
int mid=l+r>>1;
if(lc<=n) add(x,lc);
if(rc<=n) add(x,rc);
build(l,mid,lc),build(mid+1,r,rc);
}
void dfs(int x){
int v; siz[x]=1,f[x][1]=sum[x][1]=1;
for(int i=head[x];i;i=e[i].nxt){
v=e[i].to,dfs(v);
for(int j=siz[x];j>=1;--j)
for(int k=siz[v];k>=0;--k){
if(s[v]=='>') tmp[j+k]=(tmp[j+k]+f[x][j]*sum[v][k]%mod*c[j+k-1][j-1]%mod*c[siz[x]+siz[v]-j-k][siz[x]-j]%mod)%mod;
else tmp[j+k]=(tmp[j+k]+f[x][j]*(sum[v][siz[v]]-sum[v][k]+mod)%mod*c[j+k-1][j-1]%mod*c[siz[x]+siz[v]-j-k][siz[x]-j]%mod)%mod;
}
siz[x]+=siz[v];
for(int j=1;j<=siz[x];++j) f[x][j]=tmp[j],tmp[j]=0;
}
for(int j=1;j<=siz[x];++j) sum[x][j]=(sum[x][j-1]+f[x][j])%mod;
}
int main(){
n=read(),scanf("%s",s+2);
build(1,n,1),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;
}
dfs(1),printf("%lld\n",sum[1][n]);
return 0;
}