期望 + dp + 计数 + 策略转限制：ICPC2025沈阳E

Play It by Ear - Problem - QOJ.ac

令 posxpos_x 表示编号为 xx 的牌在原先牌堆的位置。

设 fif_i 表示完成第 ii 步（aia_i 牌打出），至少需要多少步。设对于 aia_i 这张牌，上一次出现在 preipre_i 的位置，那样子有：

fi≥fi−1+1fi≥fprei+n+1f_i\ge f_{i-1}+1\\ f_i\ge f_{pre_i} + n + 1

因为上一张牌打完之后至少要 nn 轮后才能回到手中，再经过一轮才能打出来。

当然，如果这张牌是第一次出现，那也必须满足：fi≥posai−n+1f_i\ge pos_{a_i} - n + 1，你要先拿到手里，然后再打出。

那么总共需要的轮数是 fmf_m。

这种一定能达到吗？我们考虑这个策略：

  1. 如果有需要的，立刻打
  2. 否则，打最晚需要的那一张。但至少目前手上有 n−1n-1 张，还有1张不需要的要等。因此当前打出来这张至少在 nn 轮后才需要，因此完全来得及。

我们要求 fmf_m 的期望值，我们设为 kk，那么我们可以先考虑对于每个 kk 有多少种合法的初始牌堆满足。那样子我们是能求出 posipos_i 的上界，而求 posipos_i 上界的过程相当于解很多具有有序性的不等式，我们要满足最严格的限制，那就反向跑个最长路即可（其实就是一个链状DAG上dp）

image-20261016165658542

考虑我们求出从 mm 到每个位置的最长路 wiw_i，然后假设对于牌 xx，第一次在 ii 的地方出现，那就要满足：

max⁡(0,posi−n+1)≤fi=k−wi\max(0,pos_i-n + 1)\le f_i=k - w_i

令 Li=k+n−wi−1L_i=k + n - w_i-1 代表 posipos_i 的上界，注意 LiL_i 还要和 2n2n 取min。

接下来就简单了，对 LiL_i 排序，然后得到 Li′L_i'，那样子期望步数小于等于 kk 的方案为：

C(k)=∏i=12n(Li−i+1)C(k)=\prod_{i=1}^{2n}(L_i-i+1)

接下来对 CC 做一个差分即可。

可以发现，有效的 kk 的取值至多 n+1n+1 个（实际上是 nn 个）。kk 的最小有效值是 w0w_0，代入 (k−w0)+n−1(k-w_0)+n-1，也就是 kk 增加 n+1n+1 次之后必然达到 2n2n 了。

还有，我们不可能每次都对 LiL_i 排序一遍，但可以发现 LiL_i 的顺序是不变的，所以提前排一次就行了。

时间复杂度 O(m+n2)O(m+n^2)

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
#include<bits/stdc++.h>
#include<cassert>
using namespace std;bool Mbe;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
#define M 200010
#define mo 998244353
#define N 200010
int pw(int a, int b) {
	int ans = 1; 
	while(b) {
		if(b & 1) ans *= a; 
		a *= a; b >>= 1; 
		ans %= mo; a %= mo; 
	}
	return ans; 
}
int pw(int a) { return pw(a, mo - 2); }
int fac[N], inv[N], ifac[N]; 
void init(int n) {
	int i; 
	for(i = fac[0] = 1; i <= n; ++i) fac[i] = fac[i-1] * i % mo; 
	ifac[n] = pw(fac[n], mo-2); 
	for(i = n - 1; i >= 0; --i) ifac[i] = ifac[i+1] * (i+1) % mo; 
    for(i = 1; i <= n; ++i) inv[i] = ifac[i] * fac[i-1] % mo; 
}
int C(int n, int m) {
	if(m > n) return 0;
	return fac[n] * ifac[m] % mo * ifac[n - m] % mo; 
}
inline void Mod(int &a) { if(a >= mo || a <= -mo) a %= mo; if(a < 0) a += mo; }
inline void Add(int &a, int b) { a += b; Mod(a); }
inline void Mul(int &a, int b) { Mod(b); a *= b; Mod(a); } 
const int iv2 = pw(2, mo - 2); 
int n, m, i, j, k, T;
int pre[M], c[M], a[M], w[M], L[M], id[M]; 
int ans, cnt, lst; 

void reset() {
	fill(a, a + m + 2, 0); 
	fill(pre, pre + 2 * n + 2, 0); 
	fill(w, w + m + 2, 0); 
	fill(c, c + 2 * n + 2, 0);
	fill(L, L + 2 * n + 2, 0); 
	fill(id, id + 2 * n + 2, 0);  
	ans = lst = cnt = 0; 
}

bool Med; signed main() {
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	  atexit([]{fprintf(stderr,"%.lfms\n%lfMB\n",clock()*1000./CLOCKS_PER_SEC,(&Mbe-&Med)/1024./1024);});
	#endif
//	srand(time(NULL));
	init(M - 1); 
	T = read();
	while(T--) {
		n = read(); m = read(); 
		reset(); 
		for(i = 1; i <= m; ++i) 
			a[i] = read(), pre[i] = c[a[i]], c[a[i]] = i; 
		w[m + 1] = -1; 
		for(i = 1; i <= m; ++i) debug("%lld ", pre[i]); debug("\n"); 
//		for(i = 1; i <= 2 * n; ++i) debug("%lld ", c[i]); debug("\n"); 
		for(i = m; i >= 0; --i) {
			w[i] = max(w[i], w[i + 1] + 1); 
			if(pre[i]) w[pre[i]] = max(w[pre[i]], w[i] + n + 1); 
		}
		for(i = 0; i <= m; ++i) debug("%lld ", w[i]); debug("\n"); 
		k = w[0]; 
		for(i = m; i >= 1; --i) c[a[i]] = i; 
		for(i = 1; i <= 2 * n; ++i) {
			if(c[i]) L[i] = min(2 * n, k + n - 1 - w[c[i]]); 
			else L[i] = 2 * n; 
		}
		for(i = 1; i <= 2 * n; ++i) id[i] = i; 
		sort(id + 1, id + 2 * n + 1, [] (int x, int y) {
			return L[x] < L[y]; 
		}); 
		for(i = 1; i <= 2 * n; ++i) debug("%lld ", id[i]); debug("\n"); 
		for(i = 1; i <= 2 * n; ++i) debug("%lld ", L[id[i]]); debug("\n"); 
		for(k = w[0]; k <= w[0] + n + 1; ++k) {
			cnt = 1; 
			for(j = 1; j <= 2 * n; ++j) {
				i = id[j]; 
				if(c[i]) L[i] = min(2 * n, k + n - 1 - w[c[i]]); 
				else L[i] = 2 * n; 
				if(L[i] - j + 1 > 0) Mul(cnt, L[i] - j + 1); 
				else cnt = 0; 
			}
				
			debug("For %lld : %lld\n", k, cnt); 
			Add(ans, (cnt - lst) * k); 
			lst = cnt; 
		}
		Mul(ans, ifac[2 * n]); 
		printf("%lld\n", ans); 
	}

	return 0;
}