LOJ

分析

假设 > 是没有限制的，那么整个序列被 < 划分为若干段。设这些段的长度为 $a_1,a_2,\cdots$，则方案数为
$$
\frac{n!}{a_1!a_2!\cdots}
$$
有 > 的限制时可以考虑容斥。设 $dp_i$ 表示前 $i$ 个数的合法序列数，容易得到
$$
dp_i=\sum_{j=0}^{i-1}(-1)^{cnt_{i-1}-cnt_j}{i\choose j}dp_j
$$
进而有
$$
\frac{dp_i}{i!}=\sum_{j=0}^{i-1}(-1)^{cnt_{i-1}-cnt_j}\frac{dp_j}{j!}\frac{1}{(i-j)!}
$$
边界为 $dp_0=0$。将 $(-1)^{cnt_{i-1}}$ 提出后分治 NTT 即可。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;
const int mod=998244353;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

char s[N]; int n;
int fac[N],ifac[N];


int r[N];
void NTT(int* A,int n,int op) {
    for (int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (int i=1;i<n;i<<=1) {
        int rot=qpow(op==1?3:(mod+1)/3,(mod-1)/(i<<1));
        for (int j=0;j<n;j+=i<<1)
            for (int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
            }
    }
    if (op==-1) { int inv=qpow(n,mod-2);
        for (int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod;
    }
}

int dp[N],cnt[N];
int F[N],G[N];
void solve(int L,int R) {
    if (L==R) {
        if (!L) dp[L]=1;
        else dp[L]=cnt[L]&1?mod-dp[L]:dp[L];
        return;
    }
    int mid=(L+R)>>1;
    solve(L,mid);
    int lim=1,l=0;
    for (;lim<=mid-L+R-L+1;lim<<=1,++l);
    for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    for (int i=0;i<=mid-L;++i) {
        if (s[i+L]=='<'&&i+L!=0) F[i]=0;
        else F[i]=cnt[i+L]&1?dp[i+L]:mod-dp[i+L];
    }
    for (int i=mid-L+1;i<lim;++i) F[i]=0;
    for (int i=0;i<=R-L+1;++i) G[i]=ifac[i];
    for (int i=R-L+2;i<lim;++i) G[i]=0;
    NTT(F,lim,1),NTT(G,lim,1);
    for (int i=0;i<lim;++i) F[i]=1ll*F[i]*G[i]%mod;
    NTT(F,lim,-1);
    for (int i=mid+1;i<=R;++i) dp[i]=(dp[i]+F[i-L])%mod;
    solve(mid+1,R);
}

int main() {
    scanf("%s",s+1); n=strlen(s+1); s[++n]='>';
    fac[0]=1;
    for (int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
    for (int i=1;i<=n;++i) cnt[i]=cnt[i-1]+(s[i]=='>');
    solve(0,n);
    printf("%d\n",1ll*dp[n]*fac[n]%mod);
    return 0;
}