ARC153E 题解

First Post:

Last Update:

很牛逼的题啊，虽然感觉自己跟正解已经差得不多了，但还是没做出来。

两点启发：

1. 设计状态时尽量设计转移跨度较小的，能多次转移的问题就不要一次转移全解决

2. 二维的 DP 状态放在平面上考虑，有时会得到格路等有用性质

首先考虑 的过程。如果当前决策的元素比当前的队头大，将其加到队头显然不优，否则显然不劣。

回到 序列中，那么加入队头的元素是一段递增前缀 ，而 对应到 ，则是 中的非严格前缀最小值。

假如说我们枚举一个 ，那么就是将 插入到 中，使得 是 的前缀最小值。

设 表示最小的 使得 。

那么设 表示左边当前插入到 ，右边当前插入到 ，那么有转移：

初始设 ，跑这个 DP 即可做到 。

注意到这个状态是二维的，放在平面上考虑，发现其只会转移到相邻的点。

从大到小枚举 ，每次将 相同的一个连续段 一起转移，求出 右边第一个 的位置 ，那么 的转移就是一个格路计数，可以直接算出通过这个连续段， 从 转移到 的方案，是个与 有关的组合数。NTT 即可完成转移，转移完之后，将 的 DP 值赋为 ，然后转移下一个连续段。这个算法复杂度是 的，因为值域很小所以可以通过。

后半段比较潦草，可以看代码理解。

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
#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 19) | 5,P = 998244353;
inline int Add(const int &a,const int &b) { return (a + b >= P) ? (a + b - P) : (a + b);}
inline int Sub(const int &a,const int &b) { return (a < b) ? (a - b + P) : (a - b);}
inline int qpow(int a,int b) { int res = 1;while(b) { if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
const int G = 3,Gi = qpow(G,P - 2);
int rev[N];
inline void calc_rev(int len) {
	for(int i = 0;i < len;i++) {
		rev[i] = rev[i >> 1] >> 1;
		if(i & 1) rev[i] |= len >> 1;
	}
}
int Gs[N],Gs2[N];
inline int GetLen(int x) {
	int len = 1;
	while(len <= x) len <<= 1;
	return len;
}
inline void initG(int len) {
	for(int i = 1;i < len;i <<= 1) {
		Gs[i] = Gs2[i] = 1;
		Gs[i + 1] = qpow(G,(P - 1) / (i << 1));
		Gs2[i + 1] = qpow(Gi,(P - 1) / (i << 1));
		for(int j = 2;j < i;j++)
			Gs[i + j] = 1ll * Gs[i + j - 1] * Gs[i + 1] % P,
			Gs2[i + j] = 1ll * Gs2[i + j - 1] * Gs2[i + 1] % P;
	}
}
inline void FFT(int *F,int len,int type) {
	for(int i = 0;i < len;i++)
		if(i < rev[i]) swap(F[i],F[rev[i]]);
	for(int k = 1;k < len;k <<= 1)
		for(int j = 0;j < len;j += k + k)
			for(int i = 0;i < k;i++) {
				int cur = type == 1 ? Gs[k | i] : Gs2[k | i];
				int u = F[i | j],v = 1ll * cur * F[i | j | k] % P;
				F[i | j] = Add(u,v);
				F[i | j | k] = Sub(u,v);
			}
	if(type == -1)
		for(int i = 0,Inv = qpow(len,P - 2);i < len;i++)
			F[i] = 1ll * F[i] * Inv % P;
} 

int n,fac[N],inv[N],ifac[N];
inline void init(int n) {
	fac[0] = 1;
	for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
	inv[1] = 1;
	for(int i = 2;i <= n;i++) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
	ifac[0] = 1;
	for(int i = 1;i <= n;i++) ifac[i] = 1ll * ifac[i - 1] * inv[i] % P;
}
inline int C(int n,int m) { if(n < 0 || m < 0 || n < m) return 0;return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
char s[N];
int tf[N],tg[N],ans[N];
int main() {
	scanf("%s",s + 1);
	n = strlen(s + 1);
	initG(1 << 19);
	init(n);
	int lim = n;
	for(int i = 1;i < n;i++)
		if(s[i] > s[i + 1]) {lim = i;break;}
	for(int i = 1;i <= lim;i++) ans[i] = 1;
	int len = GetLen(n + n + 2);
	calc_rev(len);
	
	for(int c = '9';c >= '1';c--) {
		int tl,tr,ct;
		tl = tr = ct = -1;
		for(int i = 1;i <= n;i++) if(s[i] == c) { tl = i;break;}
		if(tl == -1 || tl > lim) continue;
		tr = tl;while(tr < n && s[tr + 1] == c) ++tr;
		ct = tr + 1;
		while(ct <= n && s[ct] > c) ++ct;

		for(int i = 0;i < len;i++) tf[i] = tg[i] = 0;
		for(int i = tr;i < ct;i++) tf[i] = ans[i];
		for(int i = 0;i < ct - tr;i++) tg[i] = C(tr - tl + i,i);
		FFT(tf,len,1);FFT(tg,len,1);
		for(int i = 0;i < len;i++) tf[i] = 1ll * tf[i] * tg[i] % P;
		FFT(tf,len,-1);
		for(int i = tr;i < ct;i++) ans[i] = tf[i];
		for(int i = tl;i < tr;i++) ans[i] = 1;
	}
	cout << ans[n] << endl;
	return 0;
}
≡