给定一个字符串ss,仅包含 <> 两种字符。

你需要计算「使得pi<pi+1p_i < p_{i + 1}当且仅当 sis_i< 的排列 」的数量。

可以发现,答案可能很大,因此你只要输出它对 998244353998244353 取模的结果。

n105n \le 10^5

LOJ 575

Solution

注意到若sis_i>pi,pi+1p_i, p_{i + 1}的大小关系任意,问题就等价于将1n1 \sim n填入若干个单增区间的方案数。设各个单增区间长度为 ,则方案数即为:

n!i=1kai \frac{n!}{\prod_{i=1}^{k} a_i}

考虑对1i=1kai\displaystyle \frac{1}{\prod_{i=1}^{k} a_i}进行DP,设f(i)f(i)表示长度为ii的前缀的合法排列除以i!i!的结果,cnticnt_i表示 > 的数量

转移考虑枚举最近的大于号的位置,设为jj,那么f(i)=f(j)×1ijf(i) = f(j) \times \frac{1}{i - j}

但断点处可能不合法,即可能和前一个单增区间连在一起,所以在前一个处减掉,如此容斥

分治FFT优化即可,复杂度O(nlog2n)O(n \log^2 n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 1e5;
const int MOD = 998244353;

namespace MATH
{
int fac[MAXN + 5], ifac[MAXN + 5], inv[MAXN + 5];

inline void ADD (int &a, int b) { if ((a += b) >= MOD) a -= MOD; }

inline int Pow (int a, int b)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL) a * a % MOD) if (i & 1) ans = (LL) ans * a % MOD;
return ans;
}

inline void init (int n = MAXN + 1)
{
fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = (LL) fac[i - 1] * i % MOD;
ifac[n] = Pow (fac[n], MOD - 2); for (int i = n - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % MOD;
for (int i = 0; i < n; ++i) inv[i + 1] = (LL) fac[i] * ifac[i + 1] % MOD;
}

inline int C (int n, int m) { if (n < m || n < 0 || m < 0) return 0; return (LL) fac[n] * ifac[m] % MOD * ifac[n - m] % MOD; }
}

using namespace MATH;

namespace Poly
{
const int MAX_LEN = MAXN * 4;
const int g = 3;

int n, rev[MAX_LEN + 5];
int LIM, omega[MAX_LEN + 5];

inline void init () // should init at the beginning
{
for (LIM = 1; LIM <= MAXN << 1; LIM <<= 1);
for (int Wn = Pow (g, (MOD - 1) / LIM), i = 0, W = 1; i <= LIM; ++i, W = (LL) W * Wn % MOD) omega[i] = W;
}

inline void dft_init (int N, int M)
{
for (n = 1; n <= N + M; n <<= 1);
for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) + ((i & 1) ? (n >> 1) : 0);
}

inline void dft (int *A, int fg)
{
for (int i = 0; i < n; ++i) if (rev[i] < i) swap (A[i], A[rev[i]]);

for (int mid = 1; mid < n; mid <<= 1)
for (int i = 0, k = LIM / (mid << 1); i < n; i += mid << 1)
for (int j = 0; j < mid; ++j)
{
int W = fg > 0 ? omega[j * k] : omega[LIM - j * k];
int x = A[i + j], y = (LL) W * A[i + j + mid] % MOD;
A[i + j] = (x + y) % MOD, A[i + j + mid] = (x - y + MOD) % MOD;
}

if (fg < 0) for (int i = 0, inv = Pow (n, MOD - 2); i < n; ++i) A[i] = (LL) A[i] * inv % MOD;
}

inline void mul (int *A, int N, int *B, int M, int *C)
{
dft_init (N, M);

static int F[MAX_LEN + 5], G[MAX_LEN + 5];
for (int i = 0; i < n; ++i) F[i] = i <= N ? A[i] : 0;
for (int i = 0; i < n; ++i) G[i] = i <= M ? B[i] : 0;

dft (F, 1), dft (G, 1);
for (int i = 0; i < n; ++i) F[i] = (LL) F[i] * G[i] % MOD;
dft (F, -1);

for (int i = 0; i <= N + M; ++i) C[i] = F[i];
}
}

int N;
char S[MAXN + 5];

int F[MAXN + 5], coef[MAXN + 5], _coef[MAXN + 5];

inline void divide (int l, int r)
{
if (l == r)
{
if (l == 0) return ;
F[l] = (LL) F[l] * _coef[l - 1] % MOD;
return ;
}

int mid = (l + r) >> 1;

divide (l, mid);

static int A[MAXN * 4 + 5], B[MAXN * 4 + 5];
int n = -1, m = -1;

for (int i = l; i <= mid; ++i) A[++n] = (LL) F[i] * coef[i] % MOD;
for (int i = 0; i <= r - l; ++i) B[++m] = ifac[i];

Poly :: mul (A, n, B, m, A);

for (int i = mid + 1; i <= r; ++i) ADD (F[i], A[i - l]);

divide (mid + 1, r);
}

inline void Solve ()
{
coef[0] = _coef[0] = F[0] = 1;

for (int i = 1; i <= N; ++i) _coef[i] = coef[i] = (S[i] == '>') ? (MOD - coef[i - 1]) : coef[i - 1];
for (int i = 1; i < N; ++i) if (S[i] == '<') coef[i] = 0;

divide (0, N);

cout << (LL) F[N] * fac[N] % MOD << endl;
}

inline void Input ()
{
scanf("%s", S + 1);
N = strlen (S + 1) + 1;
}

int main ()
{

#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

MATH :: init ();
Poly :: init ();
Input ();
Solve ();

return 0;
}