LOJ 575. Unequal relation

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:

  1. unlimited
  2. 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:

\[(-1)^{t}\sum \frac{n!}{\prod (-c_i!)} \]

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

\[f_i=-\prod f_j\times \frac{1}{(i-j)!} \]

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 ;
}

Posted by Fife Club on Mon, 16 May 2022 00:54:09 +0300