题解：
我们可以将大于号当成从左向右的边，将小于号当成一条从右向左的边
首先忽略大于号，只考虑小于号，那么图显然应该由一个个只包含同向边的连通块所构成
此时满足要求的排列方法显然为$frac{n!}{sum siz_i!}$
我们只能用这种方法解决同向边约束的图，那么怎么解决包含大于号即图中边不同向的约束呢？
容斥！
$ans=忽略大于号的方案数-将1个大于号改成小于号的方案数+将2个大于号改成小于号的方案数-……$
用二项式定理可以验证
然后我们设$dp_i$ 表示满足前i个数约束的方案数，假如向下一个点向该点有一条从向右向左的边，那么这两个点得到容斥答案是重复的，只计算一个即可
所以我们只需要计算$s_i=‘>’$，即向下一个点有从左向右的边的点
可以推得：$dp_i=i![s_i='>']sumlimits_{j=0}^{i-1} [s_j='<']*(-1)^{cnt[i-1]-cnt[j]}*frac{1}{(i-j)}*dp[j]/ j!$
cnt[i]表示i点及以前有多少个大于号
然后这个柿子可以化成$frac{dp_i}{i}*(-1)^{cnt[i]}=$
$[s_i='>']*(-1)^{cnt[i]}+cnt[i-1]} sumlimits_{j=0}^{i-1} [s_j='<']*frac{1}{(i-j)}*frac{dp[j]}{ j!}*(-1)^{cnt[j]}$
分治ntt即可
#include<bits/stdc++.h> #define maxn 100005 #define maxm 500005 #define inf 0x7fffffff #define ll long long #define rint register int #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define rep(i,a,b) for(int i=a;i<=b;i++) #define dgx cerr<<"=============="<<endl #define MAXN 540050 #define lowbit(x) (x&(-x)) using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while('0'>ch || ch>'9'){if(ch=='-') f=-1; ch=getchar();} while('0'<=ch && ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const ll mod=998244353; ll ksm(ll x,ll y){ ll res=1; while(y){ if(y&1) res=(res*x)%mod; x=(x*x)%mod; y>>=1; } return res; } int wk(int x){ if(x&1) return mod-1; return 1; } ll Mod(ll x){ x%=mod; if(x<0) x+=mod; return x; } char s[MAXN]; ll ans=0,F[MAXN],G[MAXN],Wn,w,z1,z2,g=3,gi,fac[MAXN],a[MAXN],b[MAXN]; int n,cnt[MAXN],rev[MAXN][20]; void ntt(ll *A,int type,int limits,int tmp){ rep(i,0,limits-1) if(rev[i][tmp]>i) swap(A[i],A[rev[i][tmp]]); for(int R=2;R<=limits;R<<=1){ int mid=(R>>1); if(type==1) Wn=ksm(g,(mod-1)/R); else Wn=ksm(gi,(mod-1)/R); for(int j=0;j<limits;j+=R){ w=1; rep(k,0,mid-1){ z1=A[j+k]; z2=A[j+k+mid]*w%mod; A[j+k]=(z1+z2)%mod; A[j+k+mid]=(z1-z2+mod)%mod; w=(w*Wn)%mod; } } } } void cdq(int l,int r,int limits,int tmp){ if(l==r){ if(!l) F[l]=mod-1; else if(s[l] =='>')F[l]=Mod(F[l]*wk(cnt[l]+cnt[l-1])); else F[l]=0; return; } int mid=(l+r)>>1; cdq(l,mid,limits>>1,tmp-1); rep(i,0,limits-1) a[i]=b[i]=0; rep(i,l,mid) a[i-l]=F[i]; rep(i,0,limits-1) b[i]=G[i];//cout<<"l="<<l<<" "<<"R="<<r<<endl; ntt(a,1,limits,tmp); ntt(b,1,limits,tmp); rep(i,0,limits-1) a[i]=(a[i]*b[i])%mod; ntt(a,-1,limits,tmp) ; rep(i,mid+1,r) F[i]=(F[i]+a[i-l]*fac[limits])%mod; cdq(mid+1,r,limits>>1,tmp-1); } ll jc(ll x){ ll res=1; rep(i,1,x) res=(res*i)%mod; return res; } int main(){ int limits=1,tmp=-1; cin>>(s+1); gi=ksm(g,mod-2); n=strlen(s+1); s[++n]='>'; s[0]='>'; cnt[0]=1; G[0]=1; rep(i,1,n) if(s[i]=='>') cnt[i]=cnt[i-1]+1; else cnt[i]=cnt[i-1]; rep(i,1,MAXN-1) fac[i]=ksm(i,mod-2),G[i]=G[i-1]*fac[i]%mod; while(limits<=n+n) limits<<=1,tmp++; rep(i,0,tmp){ rep(j,0,(1<<(i+1))-1) rev[j][i]=(rev[j>>1][i]>>1)|((j&1)<<i); } cdq(0,limits-1,limits,tmp); printf("%lld",Mod(F[n]*wk(cnt[n]))*jc(n)%mod); return 0; }