博弈论找性质mex用容斥+NTT优化：26暑杭电 2-05

1005 减数游戏 2

博弈

先把博弈论的问题解决掉，怎样是最优的。

目的是让对手尽可能地吃掉有的数

我们来看一个数轴：

只要蓝色是先手：

• 奇数连续段时，它必然比绿色少吃1个
• 偶数段时，它和绿色相等

而且通过上面这种策略，它每次都可以占据空白段。

因此，关键在于谁能获得空白段的主动权

而空白段的主动权，只和第一个连续段的长度有关。

如果第一个连续段长度为偶数，那么先手就必胜了。

容斥

不妨令 $\text{mex}(S)=p$，在 $1\sim p-1$ 内有 $r$ 个空，总共有 $b$ 个数可以选。那么首先 $p$ 这个位置一定为空且不能选，因此剩余可以选的位置有 $n-1$ 个。

我们要算的是，这 $r$ 个空都被填上，即有恰好0个空没被人填上。我们考虑容斥，设有至少 $i$ 个空没被填上，则：

$$\begin{align*} ans_p&=\sum_{i=0}^r\binom{r}{i}(n-1-i)^b(-1)^i\\ &=\sum_{i=0}^r\frac{r!\cdot (n-1-i)^b(-1)^i}{i!\cdot(r-i)!}\\ &=r!\cdot\sum_{i+j=r}\frac{(-1)^i(n-1-i)^b}{i!}\cdot \frac 1 {j!} \end{align*}$$

令：

$$F_i(x)=\sum_{i}\frac{(-1)^i(n-1-i)^b}{i!}\cdot x^i\\[6pt] G_i(x)=\sum_{i}\frac 1 {i!}\cdot x^i$$

则答案为：

$$\sum_{p为奇数}[x^r](F\cdot G)r!$$

复杂度 $O(n\log n)$

$p=n+1$ 的情况要单独计算一下。

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

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
	T = read();
	init(100000); 
	while(T--) {
		n = read(); 
		for(i = 0; i <= n; ++i) c[i] = 0;  
		for(i = 1; i <= n; ++i) c[read()]++; 
		b = c[0]; ans = 0; 
		vector<int>f(n + 1), g(n + 1); 
		for(i = 0, fu = 1; i <= n - 1; ++i, fu = -fu) {
			f[i] = fu * pw(n - 1 - i, b) % mo * ifac[i] % mo; 
			g[i] = ifac[i]; 
		}
		auto t = convolution(f, g); 
		for(i = 1, r = 0; i <= n; i += 2) {
			if(!c[i] && b >= r) {
				Add(ans, t[r] * fac[r] % mo); 	
			}
			r += (c[i] == 0); r += (c[i + 1] == 0); 
		}
		if(n % 2 == 0) {
			for(i = 1; i <= n; ++i) if(c[i] > 1) break; 
			if(i > n) {
				Add(ans, fac[b]); 
			}
		}
		printf("%lld\n", ans); 
	}

	return 0;
}