CF1654H Three Minimums

题面传送门
原来CF的机子是32位的，还可以手动切到64位，卡常把人卡傻掉了。
题目中要求最小值首先考虑\(1\)的位置，记为\(i\)，那么显然所有形如\([j,i](j\leq i)\)的区间，最小值都在\(i\)，对于\([i,j](j\geq i)\)也是如此。
然后考虑\([1,i]\)区间内的第二小值，记位置为\(j\)，那么显然\([1,j]\)变成了一个子问题，\([j,i]\)是一个先单调上升再单调下降的序列。
可以设\(G_{i,j,1}\)为区间\([i,j]\)左边为\(1\)，右边为\(2\)的方案数，\(G_{i,j,2}\)为左\(2\)右\(1\)，随便\(O(n^2)\)转移。
然后设\(F_{i,1}\)为\([1,i]\)的方案数，那么就显然是\(F_{i,1}=\sum\limits_{j=1}^{i-1}{F_{j,1}\times G_{j,i,2}\times C_{i-2}^{j-1}}\)
\(F_{i,2}\)与\(F_{i,1}\)相反。
这样可以得到\(O(n^2)\)的dp。
然后发现如果没有限制的话那么对于所有等长的区间，\(G\)的值是等价的，唯一要考虑的是限制，那么可以对限制单独\(O(nm)\)转移，剩下的设长度为\(i\)的方案数为\(P_i\)，则\(P_2=1,P_i=2^{i-3},i\geq 3\)。
然后对于\(F\)实际上可以直接分治NTT就可以解决了。
最后枚举最小值所在位置是平凡的。时间复杂度\(O(n\log ^2n+nm)\)
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N ((1<<19)+5)
#define M (100+5)
#define K (200000+5)
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;
int n,m,A[K],B[K],E[N],D[N],frc[K],Inv[K],P[K],G1[M][K],G2[M][K],F1[K],F2[K];ll Ans;char S[M];
I int mpow(int x,int y=mod-2){ll Ans=1;while(y) y&1&&(Ans=1ll*Ans*x%mod),y>>=1,x=1ll*x*x%mod;return Ans;}const int G=3,InvG=mpow(G);
I int C(int x,int y){return 1ll*frc[x]*Inv[y]%mod*Inv[x-y]%mod;}
int tr[N],k;I void Init(int n){k=1;while(k<=n+1)k<<=1;for(RI i=0;i>1]>>1)|(i&1?k/2:0),E[i]=D[i]=0;}
I void NTT(int *A,int n,int flag){
	RI i,j,h,key,now,pus;for(i=0;i>1,L1=m-l+1,L2=r-m;Solve(l,m,op,F);Init(L1*2+L2);for(i=0;im?(A[i]=B[i]=1):(S[i]^'<'?(A[i]=1):(B[i]=1));
	for(frc[0]=Inv[0]=i=1;i<=n;i++) frc[i]=1ll*frc[i-1]*i%mod,Inv[i]=mpow(frc[i]);
	for(P[2]=P[3]=1,i=4;i<=n;i++) P[i]=P[i-1]*2%mod;
	for(i=m;i;i--){G2[i][i+1]=A[i];G1[i][i+1]=B[i];G1[i][i+2]=G2[i][i+2]=B[i]*A[i+1];
		for(j=i+3;j<=n;j++)G1[i][j]=G2[i][j]=B[i]*A[j-1]*((i^m?G2[i+1][j]:P[j-i])+G1[i][j-1])%mod;
	}
	Solve(1,n,1,F1);Solve(1,n-m,0,F2);reverse(F2+1,F2+n+1);for(i=m;i;i--) for(j=i+1;j<=n;j++) F2[i]=(F2[i]+1ll*F2[j]*G1[i][j]%mod*C(n-i-1,n-j))%mod;
	//for(F1[1]=1,i=2;i<=n;i++) for(j=1;j