【UOJ401】【CTSC2018】青蕈领主

发表于 | 更新于
http://uoj.ac/problem/401

题目链接

【UOJ401】【CTSC2018】青蕈领主

做法

参考自这篇文章。
最长连续序列不能相交，那么只有包含关系。
那么我们可以根据区间的包含关系建出一棵以 $ n $ 为根的树，用 $ dis[i] $ 表示节点 $ i $ 的儿子个数。
因为连续的区间可以看成一个点，所以每个节点的贡献可以分别考虑。
设 $ f[i] $ 为长度为 $ i $ 且有多少个长度为 $ i + 1 $ 的连续序列，删去最大数后不存在长度超过 $ 1 $ 的连续序列，答案为 $ \prod { f[dis[i]] } $ 。
若 $ f[i] $ 如果从合法方案转来，只要最后一个数不等于 $ i $ 即可，方案数为 $ (i − 1) \times f[i − 1] $ 。
否则，那么不满足的区间只有有一个，长度设为 $ l $ ，把最大值插入形成合法区间的方案数为 $ f[l] $ ,把插入后的区间看成一个点，与剩下的点的方案数为 $ f[i − l] $ ；若要保证有解，那么这个区间的范围一定在 $ [2,i − l] $ ，所以得到：
$$ f[i] = (i - 1) \times f[i - 1] + \sum_{l = 2}^{i - 2}{(i - l - 1) \times f[i]f[i - l]} $$
分治 $ FFT $ 即可。 

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
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int mod = 998244353;

inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
inline int add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }
inline int sub(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int mul(int x, int y) { return (int)((ll)x * y % mod); }
inline int ksm(int x, int y = mod - 2) {
	int ss = 1; for(; y; y >>= 1, x = mul(x, x)) if(y & 1) ss = mul(ss, x);
	return ss;
}
namespace Poly {
	inline int Get(int x) { int ss = 1; for(; ss <= x; ss <<= 1); return ss; }
	void ntt(vector<int> &A, int lmt, int opt) {
		A.resize(lmt + 5);
		for(int i = 0, j = 0; i < lmt; i++) {
			if(i > j) swap(A[i], A[j]);
			for(int k = lmt >> 1; (j ^= k) < k; k >>= 1);
		}
		vector<int> w(lmt >> 1);
		for(int mid = 1; mid < lmt; mid <<= 1) {
			w[0] = 1;
			int w0 = ksm(opt == 1 ? 3 : (mod + 1) / 3, (mod - 1) / mid / 2);
			for(int j = 1; j < mid; j++) w[j] = mul(w[j - 1], w0);
			for(int R = mid << 1, j = 0; j < lmt; j += R)
				for(int k = 0; k < mid; k++) {
					int x = A[j + k], y = mul(w[k], A[j + mid + k]);
					A[j + k] = add(x, y), A[j + mid + k] = sub(x, y);
				}
		}
		if(opt == -1)
			for(int i = 0, ilmt = ksm(lmt); i < lmt; i++)
				A[i] = mul(A[i], ilmt);
	}
	vector<int> Mul(const vector<int> &a, const vector<int> &b) {
		vector<int> A = a, B = b; int lmt = Get(A.size() + B.size() - 2);
		A.resize(lmt + 5), B.resize(lmt + 5), ntt(A, lmt, 1), ntt(B, lmt, 1);
		for(int i = 0; i < lmt; i++) A[i] = mul(A[i], B[i]);
		ntt(A, lmt, -1); return A.resize(A.size() + B.size() - 1), A;
	}
}
const int N = 50010;
int T, n;
int a[N], dis[N], sta[N], top = 0;
vector<int> f;

void cdq(int l, int r) {
	if(l > r) return ;
	if(l == r) {
		if(l == 2) f[l] = 2; else f[l] = add(f[l], mul(l - 1, f[l - 1]));
		return ;
	}
	vector<int> G, F; int mid = (l + r) >> 1; cdq(l, mid);
	for(int i = 0; i <= r - l + 1; i++) F.pb(f[i]);
	for(int i = 0; i <= r - l + 1; i++)
		if(i + l <= mid) G.pb(mul(f[i + l], i + l - 1));
	F = Poly::Mul(F, G);
	for(int i = mid + 1; i <= r; i++) f[i] = add(f[i], F[i - l]);
	if(l != 2) {
		F.clear(), G.clear();
		for(int i = 0; i <= r - l + 1; i++) if(i + l <= mid) F.pb(f[i + l]);
		for(int i = 0; i <= r - l + 1; i++)
			if(i <= r - l) G.pb(mul(f[i], i - 1));
		F = Poly::Mul(F, G);
		for(int i = mid + 1; i <= r; i++) f[i] = add(f[i], F[i - l]);
	}
	cdq(mid + 1, r);
}
void solve() {
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]), dis[i] = 0;
	if(a[n] != n) { puts("0"); return ; }
	int ans = 1; top = 1, sta[1] = n;
	for(int i = n - 1; i; i--) {
		for(; i < sta[top] - a[sta[top]] + 1; --top);
		if(i - a[i] < sta[top] - a[sta[top]]) { puts("0"); return ; }
		++dis[sta[top]], sta[++top] = i;
	}
	for(int i = 1; i <= n; i++) ans = mul(ans, f[dis[i]]);
	printf("%d\n", ans); return ;
}
int main() {
	scanf("%d%d", &T, &n), f.resize(n + 1), cdq(2, n - 1), f[0] = 1, f[1] = 2;
	for(; T; --T) solve();
	return 0;
}