不等關系

題解

感覺有點麻煩，可能還是我太差了，

首先我們先考慮不管">“的情況，我們得到的就是一串斷斷續續的的”<"序列，
很容易發現，連在一起的部分就是要求出一個這么長的遞增序列，
我們令這些遞增序列的長度為 { a 1 , . . . , a k } \{a_{1},...,a_{k} \} {a1?,...,ak?}，我們就是要從這 n n n個數中得到這 k k k個長度為 a a a的遞增序列，這個值是比較好算的，就是 n ! ∏ i = 1 k a i ! \frac{n!}{\prod_{i=1}^{k}a_{i}!} ∏i=1k?ai?!n!?，
相當于先得到一個 n n n的排列，將其分開后再去掉某一段內部不合法的情況，很明顯，對于任意一段，其內部合法的情況應該是唯一的，

對于含有">“的情況，我們可以通過容斥求出，
設 d p i dp_{i} dpi?表示長度為 i i i的排列合法的概率， f i f_{i} fi?表示長度為 i i i的排列的合法的情況數， c n t i cnt_{i} cnti?表示以 i i i為止的前綴中含有”>"的個數，
由于， f i = ∑ j ∈ [ 1 , i ) , s j = ′ > ′ ( ? 1 ) c n t i ? 1 ? c n t j f j C i i ? j f_{i}=\sum_{j\in[1,i),s_{j}='>'}(-1)^{cnt_{i-1}-cnt_{j}}f_{j}C_{i}^{i-j} fi?=∑j∈[1,i),sj?=′>′?(?1)cnti?1??cntj?fj?Cii?j?
故 d p i = ∑ j ∈ [ 1 , i ) , s j = ′ > ′ ( ? 1 ) c n t i ? 1 ? c n t j d p j ( i ? j ) ! dp_{i}=\sum_{j\in[1,i),s_{j}='>'}(-1)^{cnt_{i-1}-cnt_{j}}\frac{dp_{j}}{(i-j)!} dpi?=∑j∈[1,i),sj?=′>′?(?1)cnti?1??cntj?(i?j)!dpj??，
明顯，如果直接算概率的話會更好算些，答案為 n ! d p n n!dp_{n} n!dpn?，

但如果直接這樣dp的話是 O ( n 2 ) O(n^2) O(n2)的，只有40pts，
但我們很快就發現上面的式子可以通過多項式算出來，但如果順著跑 N T T NTT NTT的話是會T飛的，不會真有人順著跑吧，
所以我們要分治NTT，總共NTT的次數還是 n n n級別的，但由于兩次相乘的多項式長度相近，常數會更小，

時間復雜度 O ( n l o g ? n ) O\left(nlog\, n\right) O(nlogn)，

原始碼

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int mo=998244353;
const int G=3,invG=332748118;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
int n,fac[MAXN],inv[MAXN],f[MAXN],cnt[MAXN],dp[MAXN];
int lim,rev[MAXN],a1[MAXN],b1[MAXN];
char str[MAXN];
inline int add(int x,int y){return x+y<mo?x+y:x+y-mo;}
inline int qkpow(int a,int s){int t=1;while(s){if(s&1)t=1ll*a*t%mo;a=1ll*a*a%mo;s>>=1;}return t;}
void init(){
	fac[0]=fac[1]=inv[0]=inv[1]=f[1]=1;
	for(int i=2;i<=2e5;i++){
		fac[i]=1ll*fac[i-1]*i%mo;
		f[i]=1ll*f[mo%i]*(mo-mo/i)%mo;
		inv[i]=1ll*inv[i-1]*f[i]%mo;
	}
}
void gray(int len){
	lim=1;int L=0;while(lim<len)lim<<=1,L++;
	for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<L-1);
}
void NTT(int *A,const int typ){
	for(int i=0;i<lim;i++)if(i<rev[i])swap(A[i],A[rev[i]]);
	for(int mid=1;mid<lim;mid<<=1){
		const int W=qkpow(typ^1?invG:G,(mo^1)/(mid<<1));
		for(int i=0;i<lim;i+=(mid<<1))
			for(int j=i,Wn=1;j<i+mid;j++,Wn=1ll*Wn*W%mo){
				const int x=A[j],y=1ll*Wn*A[j+mid]%mo;
				A[j]=add(x,y);A[j+mid]=add(x,mo-y);
			}
	}
	if(typ^-1)return ;const int iv=qkpow(lim,mo-2);
	for(int i=0;i<lim;i++)A[i]=1ll*A[i]*iv%mo;
}
void sakura(int l,int r){
	if(l==r){if(l&&str[l]=='>'&&(~cnt[l]&1))dp[l]=mo-dp[l];return ;}
	int mid=l+r>>1;sakura(l,mid);gray(r-l+1);
	for(int i=0;i<lim;i++)a1[i]=b1[i]=0;
	for(int i=l;i<=mid;i++)if(str[i]=='>')a1[i-l]=cnt[i]&1?mo-dp[i]:dp[i];
	for(int i=1;i<=r-l;i++)b1[i-1]=inv[i];
	NTT(a1,1);NTT(b1,1);for(int i=0;i<lim;i++)a1[i]=1ll*a1[i]*b1[i]%mo;NTT(a1,-1);
	for(int i=mid+1;i<=r;i++)dp[i]=add(dp[i],a1[i-l-1]);sakura(mid+1,r);
}
signed main(){
	init();scanf("%s",str+1);n=strlen(str+1);str[0]=str[++n]='>';
	for(int i=1;i<=n;i++)cnt[i]=cnt[i-1]+(str[i]=='>');
	dp[0]=1;sakura(0,n);printf("%d",1ll*dp[n]*fac[n]%mo);
	return 0;
}

謝謝！！！