## LOJ 575. Unequal relation

Given a string \ (S \) with a len gt h of \ (n-1 \), it contains only < and > characters.

You need to calculate the number of permutations \ (P \) that make \ (p_i < p_ {I + 1} \) if and only if \ (S \) is <.

It can be found that the answer may be very large, so you just output the result of its modulus of \ (10 ^ 9 + 7 \).

In other words, for each position in \ (S \), if \ (S_i = \) <, then \ (p_i < p_ {I + 1} \), otherwise \ (p_i > p_ {I + 1} \)

- \(n\le 10^5\)

### Solution

From the point of view of the shape pressure of \ (2^n \), for a position, if it is < then it is set to 0, otherwise it is set to 1.

For the inclusion and exclusion of < and >, we ignore the limitation of > so that the calculated answer is equivalent to the high-dimensional prefix and sum of the answer.

Assuming that the high-dimensional prefix and array are known, if you want to get the point value at \ (S \), you only need to make the high-dimensional prefix difference. At this time, the contribution of a subset to the answer is the power of the difference in the number of \ (1 \) of \ ((- 1) \).

Considering the problem of formal description, our current problem is:

By default, the sequence is all <, the original part is > and the position is either unlimited or <. The contribution of one case to the answer is the number of schemes multiplied by the corresponding power of \ (- 1 \).

Considering the continuous <, unlimited is equivalent to segmentation.

It is not difficult to find that what we need to consider is only the number of schemes for splitting a sequence with length \ (n \) into several monotonic sequences.

Using dp to calculate the answer, we make two decisions from front to back dp, when adding a > each time:

- unlimited
- For<

In this way, we need to record the length of the end segment with a complexity of \ (\ mathcal O(n^2) \)

Considering whether the answer can be calculated directly after the division, it is not difficult to find that our answer is equivalent to the number of schemes that divide \ (n \) elements into several sets and contribute with \ ((- 1) \), that is:

More formally, record the subscript of < and find that it is equivalent to:

This recursive formula can be optimized by divide and conquer NTT.

Don't know the difference between \ (50 \) and \ (100 \), board? This is really confusing. However, I feel that I haven't written too much about riding for 80000 years. As a result, I passed without much adjustment today. I'm still very moved.

\(Code:\)

#include<bits/stdc++.h> using namespace std ; #define Next( i, x ) for( register int i = head[x]; i; i = e[i].next ) #define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i ) #define drep( i, s, t ) for( register int i = (t); i >= (s); -- i ) #define re register #define int long long int gi() { char cc = getchar() ; int cn = 0, flus = 1 ; while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; } while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ; return cn * flus ; } const int P = 998244353 ; const int Gi = 332748118 ; const int G = 3 ; const int N = 4e5 + 5 ; int fpow(int x, int k) { int ans = 1, base = x ; while(k) { if(k & 1) ans = 1ll * ans * base % P ; base = 1ll * base * base % P, k >>= 1 ; } return ans ; } int n, p[N], cnt, limit, Inv, A[N], B[N], L, R[N], Ans, fac[N], inv[N], f[N] ; char s[N] ; void init(int x) { limit = 1, L = 0 ; while( limit < x ) limit <<= 1, ++ L ; for(re int i = 0; i < limit; ++ i) R[i] = ( (R[i >> 1] >> 1) | ((i & 1) << (L - 1)) ) ; Inv = fpow( limit, P - 2 ) ; } void NTT( int *a, int type ) { for(re int i = 0; i < limit; ++ i) if( R[i] > i ) swap( a[i], a[R[i]] ) ; for(re int k = 1; k < limit; k <<= 1) { int d = fpow( (type == 1) ? G : Gi, (P - 1) / (k << 1) ) ; for(re int i = 0; i < limit; i += (k << 1) ) for(re int j = i, g = 1; j < i + k; ++ j, g = g * d % P) { int nx = a[j], ny = a[j + k] * g % P ; a[j] = (nx + ny) % P, a[j + k] = (nx - ny + P) % P ; } } if( !type ) for(re int i = 0; i < limit; ++ i) a[i] = a[i] * Inv % P ; } int st[N], top ; void CDQ(int l, int r) { if( l == r ) { if(l == 1) f[l] = 1 ; return ; } int mid = (l + r) >> 1 ; CDQ(l, mid) ; top = 0 ; for(re int i = l; i <= mid; ++ i) st[++ top] = f[i] ; for(re int i = 0; i <= top; ++ i) A[i] = st[i] ; for(re int i = 0; i <= top * 2; ++ i) B[i] = inv[i] ; init(top * 3 + 5), NTT( A, 1 ), NTT( B, 1 ) ; for(re int i = 0; i < limit; ++ i) A[i] = A[i] * B[i] % P ; NTT( A, 0 ) ; for(re int i = mid + 1; i <= r; ++ i) if( p[i] ) f[i] = ( f[i] - A[i - mid + top] + P ) % P ; for(re int i = 0; i <= limit; ++ i) A[i] = B[i] = 0 ; CDQ(mid + 1, r) ; } signed main() { fac[0] = inv[0] = 1 ; scanf("%s", s + 1 ), n = strlen(s + 1) + 1 ; rep( i, 2, n ) p[i] = ( s[i - 1] == '>' ) ? 1 : 0 ; rep( i, 1, n ) cnt += p[i] ; rep( i, 1, n ) fac[i] = fac[i - 1] * i % P, inv[i] = fpow( fac[i], P - 2 ) ; p[n + 1] = 1, CDQ(1, n + 1) ; int Ans = 0 ; if( cnt & 1 ) Ans = f[n + 1] ; else Ans = P - f[n + 1] ; Ans = Ans * fac[n] % P ; cout << Ans % P << endl ; return 0 ; }