2018-ACetic_ACid/AugTrain-03/B

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <bits/stdc++.h>
#ifdef LOCAL
#define debug 1
#else
#define debug 0
#endif

typedef long long ll;
using namespace std;
#define N 5100
const int mod=1e9+7;
int n;
char s[N];
int f[N][N],g[N][N],jc[N];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    if(n==1) 
    {
        printf("1");
        return 0;
    }
    jc[0]=1;
    for(int i=1;i<=n;i++) jc[i]=1ll*jc[i-1]*i%mod;
    f[0][0]=1;
    g[n+1][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(s[i]=='>')
            {
                (f[i][j]+=1ll*f[i-1][j]*j%mod)%=mod;
                if(j) (f[i][j]+=f[i-1][j-1])%=mod;
            }
            else
            {
                (f[i][j]+=1ll*f[i-1][j+1]*j%mod*(j+1)%mod)%=mod;
                (f[i][j]+=1ll*f[i-1][j]*j%mod)%=mod;
            }
        }
        f[i][0]=0;
    }   
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=n-i+1;j++)
        {
            if(s[i]=='<')
            {
                (g[i][j]+=1ll*g[i+1][j]*j%mod)%=mod;
                if(j) (g[i][j]+=g[i+1][j-1])%=mod;
            }
            else
            {
                (g[i][j]+=1ll*g[i+1][j+1]*j%mod*(j+1)%mod)%=mod;
                (g[i][j]+=1ll*g[i+1][j]*j%mod)%=mod;
            }
        }
        g[i][0]=0;
    }
/*  for(int i=1;i<=n;i++,cerr<<endl)
        for(int j=0;j<=n;j++)
        {
            cerr<<f[i][j]<<" ";
        }
        cerr<<endl;
    for(int i=1;i<=n;i++,cerr<<endl)
        for(int j=0;j<=n;j++)
        {
            cerr<<g[i][j]<<" ";
        }*/
    for(int i=1;i<=n;i++)
    {
        int ans=0;
        if(i==1) ans=g[2][1];
        else if(i==n) ans=f[n-1][1];
        else
        {
            for(int j=1;j<i;j++)
            {
                (ans+=2ll*f[i-1][j]%mod*g[i+1][j]%mod*jc[j]%mod*jc[j]%mod)%=mod;
                (ans+=1ll*f[i-1][j]*g[i+1][j+1]%mod*jc[j]%mod*jc[j+1]%mod)%=mod;
            }
            for(int j=1;j<n-i+1;j++)
            {
                (ans+=1ll*f[i-1][j+1]*g[i+1][j]%mod*jc[j]%mod*jc[j+1]%mod)%=mod;
            }
        }
        if(i!=1) printf(" ");
        printf("%d",ans);
    }
    return 0;
}
}}}

#include <bits/stdc++.h>
#ifdef LOCAL
#define debug 1
#else
#define debug 0
#endif
typedef long long ll;
using namespace std;
#define N 5100
const int mod=1e9+7;
int n;
char s[N];
int f[N][N],g[N][N],jc[N];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    if(n==1) 
    {
        printf("1");
        return 0;
    }
    jc[0]=1;
    for(int i=1;i<=n;i++) jc[i]=1ll*jc[i-1]*i%mod;
    f[0][0]=1;
    g[n+1][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(s[i]=='>')
            {
                (f[i][j]+=1ll*f[i-1][j]*j%mod)%=mod;
                if(j) (f[i][j]+=f[i-1][j-1])%=mod;
            }
            else
            {
                (f[i][j]+=1ll*f[i-1][j+1]*j%mod*(j+1)%mod)%=mod;
                (f[i][j]+=1ll*f[i-1][j]*j%mod)%=mod;
            }
        }
        f[i][0]=0;
    }   
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=n-i+1;j++)
        {
            if(s[i]=='<')
            {
                (g[i][j]+=1ll*g[i+1][j]*j%mod)%=mod;
                if(j) (g[i][j]+=g[i+1][j-1])%=mod;
            }
            else
            {
                (g[i][j]+=1ll*g[i+1][j+1]*j%mod*(j+1)%mod)%=mod;
                (g[i][j]+=1ll*g[i+1][j]*j%mod)%=mod;
            }
        }
        g[i][0]=0;
    }
/*  for(int i=1;i<=n;i++,cerr<<endl)
        for(int j=0;j<=n;j++)
        {
            cerr<<f[i][j]<<" ";
        }
        cerr<<endl;
    for(int i=1;i<=n;i++,cerr<<endl)
        for(int j=0;j<=n;j++)
        {
            cerr<<g[i][j]<<" ";
        }*/
    for(int i=1;i<=n;i++)
    {
        int ans=0;
        if(i==1) ans=g[2][1];
        else if(i==n) ans=f[n-1][1];
        else
        {
            for(int j=1;j<i;j++)
            {
                (ans+=2ll*f[i-1][j]%mod*g[i+1][j]%mod*jc[j]%mod*jc[j]%mod)%=mod;
                (ans+=1ll*f[i-1][j]*g[i+1][j+1]%mod*jc[j]%mod*jc[j+1]%mod)%=mod;
            }
            for(int j=1;j<n-i+1;j++)
            {
                (ans+=1ll*f[i-1][j+1]*g[i+1][j]%mod*jc[j]%mod*jc[j+1]%mod)%=mod;
            }
        }
        if(i!=1) printf(" ");
        printf("%d",ans);
    }
    return 0;
}