传送门
(ldx:You have successfully forgot to add an 'is' function to the last expression.)
(gigo:Oh you're right,,,wait a moment.)
(updateeeee 2019.10.13)
也是挺毒瘤的一道题。。
必须记录一下。
我们可以将大于号视作分割点。所以相当于做很多个单调上升序列，只是每个序列的尾巴要比下一个的头头大。
我们将序列限制转成01序列，大于号是1。
有如下容斥方式：（抄的）
我们暂且先忽略掉所有
<
。
考虑将
>
看做一个限制“1”，要求的就是
111...111
。
那么，容斥一下，就是：
111...111
=
111...11?
-
111...110
=
111...11?
-
111...1?0
+
111...100
= ...
=
111...11?
-
111...1?0
+
111...?00
- ...
考虑类似
111?000
这种怎么求
我们假设当前是一个问号，那么进行如上容斥。
设f[i]表示前i位的合法方案。
枚举上一个大于号在哪里。
两者之间的大于号决定了两者的正负相对性。
因为在这之后都是小于号，单增，所以没有顺序不同的可能性，直接组合数即可。cnt表示前i个中大于号的个数和。
所以方程是
如果用类似EGF的表示方法，每个f(i)表示其除以i!之后的答案，就能得到一个很优美的卷积形式
最后一坨是一个，前面三项是一个，卷积起来，最后乘-1的那么多次方就行。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
int in{
int cnt=0,f=1;char ch=0;
while(!isdigit(ch)){
ch=getchar();if(ch=='-')f=-1;
}
while(isdigit(ch)){
cnt=cnt*10+ch-48;
ch=getchar();
}return cnt*f;
}
char s[100003];
int n;
const int mod=998244353;
int f[100003];
int a[1000003],b[1000003],limit,l,r[1000003];
int fac[1000003],ifac[1000003];
int sum[100003],is[100003];
int _1[100003];
void getl(int len){
limit=1,l=0;
while(limit<len)limit<<=1,l++;
for(int i=0;i<limit;i++){
r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}
}
int ksm(int a,int b){
int sum=1;
while(b){
if(b&1)sum=sum*a%mod;a=a*a%mod;b>>=1;
}return sum;
}
void NTT(int *a,int len,int inv){
for(int i=0;i<len;i++)if(i<r[i])swap(a[i],a[r[i]]);
for(int mid=1;mid<len;mid<<=1){
int wn=ksm(3,(mod-1)/(mid<<1));
for(int i=0;i<len;i+=mid*2){
int omega=1;
for(int j=0;j<mid;j++,omega=omega*wn%mod){
int x=a[i+j],y=a[i+j+mid]*omega%mod;
a[i+j]=(x+y)%mod;a[i+j+mid]=(x-y+mod)%mod;
}
}
}if(inv==1)return;
int gu=ksm(len,mod-2);reverse(a+1,a+len);
for(int i=0;i<len;i++)a[i]=a[i]*gu%mod;
}
void CDQ(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
CDQ(l,mid);
getl((r-l+1)<<1);
for(int i=0;i<limit;i++)a[i]=b[i]=0;
for(int i=l;i<=r;i++)a[i-l]=ifac[i-l];
for(int i=l;i<=mid;i++){
b[i-l]=f[i]*_1[sum[i]]%mod*is[i]%mod;
}
NTT(a,limit,1);NTT(b,limit,1);
for(int i=0;i<limit;i++)a[i]=a[i]*b[i]%mod;
NTT(a,limit,-1);//for(int i=0;i<limit;i++)cout<<a[i]<<" ";cout<<endl;
for(int i=mid+1;i<=r;i++)f[i]=(f[i]+_1[sum[i-1]]*a[i-l]%mod)%mod;
CDQ(mid+1,r);
}
signed main(){
scanf("%s",s+1);n=strlen(s+1)+1;_1[0]=1;
for(int i=1;i<=n;i++)if(s[i]=='>')is[i]=1,sum[i]++;
for(int i=1;i<=n;i++)sum[i]=(sum[i-1]+sum[i])%mod,_1[i]=_1[i-1]*(mod-1)%mod;
f[0]=1;is[0]=1;
ifac[0]=fac[0]=1;ifac[0]=0;
for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
ifac[n]=ksm(fac[n],mod-2);
for(int i=n-1;i>=1;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
// for(int i=0;i<=n;i++)cout<<_1[i]<<" ";cout<<endl;
// for(int i=0;i<=n;i++)cout<<is[i]<<" ";cout<<endl;
// for(int i=0;i<=n;i++)cout<<sum[i]<<" ";cout<<endl;
// for(int i=0;i<=n;i++)cout<<fac[i]<<" ";cout<<endl;
// for(int i=0;i<=n;i++)cout<<ifac[i]<<" ";cout<<endl;
CDQ(0,n);
f[n]=f[n]*fac[n]%mod;
cout<<f[n];
return 0;
}