题解：P9537 [YsOI2023] Qingshan and Daniel 2
KK_lang
·
·
题解
好题好题好题好题好题好题好题。
这一篇写得非常牛。
【sol】
这种类型的博弈，显然不能按集合中的元素刻画，应当尝试对每个局面设置一个状态值，使其具有势能或者可以分析。
在本题中这个值是 |S| 即 S 大小。考虑一个集合 |S| 至少能生成多少个数，显然这个下界是 |S|-1，并且很容易做到 |S|（|S|-1 是 S_2-S_1,S_3-S_1\dots，显然如果存在 S_i-S_{i-1}\neq S_{i+1}-S_i，则从此处往左右扩展能生成 |S| 个数），具体地，如果 S 构成等差数列，那么只能生成 |S|-1 个数，否则能生成至少 |S| 个数。
尝试讨论 |S| 与 |T| 的相对关系。
-
若 |S|-1>|T|，则无论如何 |S| 生成的 |S|-1 个数都不会被 T 完全遮挡，并且一轮结束以后 |S'|=|S|,|T'|=|T|，故每次轮到先手，其都有牌可出，故这是先手必胜；
-
若 |S|<|T|，则先手操作一次后后手 |T|\leftarrow|T|+1，转化为上一个局面，后手必胜。
若 |S|=|T| 或 |S|=|T|+1，值得进一步讨论，下文我们讨论 |S|=|T|+1，因为对于 |S|=|T| 的局面先手操作一次之后就完全转化为了后手的 |S|=|T|+1 局面，其胜负性与这个局面是完全相反的。
声称一些性质。集合中的元素不会删除，所以其最大最小值都是单调的、极差是不降的。
考虑在最终局面下我们必须让 S 是等差序列，且 T 恰好是公差的整倍数序列。换句话说，在最终局面中，|S|=|T|+1 同样成立，设 |T|=m，则：
一种情况是初始局面就是这个，这是合法的，否则一定经过了至少一次操作。考虑结束前最后一回合，后手进行最后一次操作后转化为上述最终局面，此时先手无法操作，注意到这个操作进行时后手集合就是上述集合，所以后手生成的数一定是 $td,t\in\{1,2,\dots,m-1\}$。
故 $a$ 一定是 $d$ 的整倍数。改写最终局面如下：
$S=\{td,(t+1)d,\dots,(t+m)d\},T=\{d,2d,\dots,md\}$。
考虑 $t=1$。因为极差是不降的，后手最后一次只能生成 $d\sim (m-1)d$，这说明整个过程中后手都不能生成 $md,(m+1)d$，所以 $S$ 最终局面中这两个元素一定是一开始就有的。
「存在 $m,d$，使初始局面下 $S,T$ 中所有数都是 $d$ 倍数，且 $S$ 中最大值与次大值分别是 $(m+1)d,md$，并且 $T$ 中最大值不超过 $md$」肯定是先手必败的必要条件。我们接下来证明，只要满足这个条件，则后手能一直有牌出，即证明其充分性。
在某一回合，$|S|=m'+1,|T|=m'$，后手能生成至少 $m'-1$ 个数，而先手看起来能生成 $m'$ 个数，但经过观察，后手生成的所有数都 $<md$，所以先手钦定最大的两个数一定起不到阻挡效果，则先手最多能阻挡 $m'-2$ 个数，$m'-2<m'-1$，故后手这一轮一定能操作。
所以 $t=1$ 的充要条件就是这个了，$t>1$ 的条件形式与这个是基本一致的。我们注意到，$t>1$ 的条件严格严于 $t=1$，新增了最小值限制，并且钦定的 $\max$ 数量更多了。所以符合 $t>1$ 一定符合 $t=1$，故我们解决了这个 case。
来到了计数环节！列出 case：
- $|S|-1>|T|$：先手必胜。
这个可以组合数。
- $|S|<|T|$：后手必胜。
这个可以组合数。
- $|S|=|T|+1$，且初始局面先手就输了，即 $S=\{a,a+d,a+2d,\dots,a+md\},T=\{d,2d,\dots,md\}$，此时先手必败。
枚举公差 $d$，使用 bitset 平移做这个事情，对每个 $d$ 求出符合条件的 $a$ 个数，复杂度 $O(\frac{V^2\log V}{w})$。
- $|S|=|T|+1$，若存在 $m,d$，使 $S,T$ 中所有数都是 $d$ 倍数，且 $S$ 中最大值与次大值分别是 $(m+1)d,md$，并且 $T$ 中最大值不超过 $md$，则先手必败，否则先手必胜。
枚举 $d$，找到一对相邻的 $d$ 的整倍数作为 $md,(m+1)d$，设 $\leq md$ 的数共 $a$ 个，可以枚举 $b=|T|$，方案数表示为：
$\sum_{b=1}^a\binom{a}{b}\binom{a-1}{b-1}$，其意义为选取 $T$ 以及选取 $S$ 中除 $md,(m+1)d$ 外的其它 $b-1$ 个元素。
通过范德蒙德卷积的推导，这个表示为 $\binom{2a-1}{a-1}$。
这个复杂度是调和级数的，$O(V\log V)$。
- $|S|=|T|+1$，若存在 $m,d$，使 $S,T$ 中所有数都是 $d$ 倍数，且 $T$ 中最大值与次大值分别是 $(m+1)d,md$，并且 $S$ 中最大值不超过 $md$，且 $|S|>1$，则先手必胜，否则先手必败。
与上一个情况完全对称。
注意第三个情况中 $a=td$ 的一些去重。
最终复杂度为 $O(\frac{V^2\log V}{w}+V\log V)$，可以通过此题。
**【code】**
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int nr = 2e4 + 10;
const int mod = 998244353;
int n, a[nr], up, fac[nr << 1], ifc[nr << 1];
int qpow(int x, int p)
{
int res = 1;
while (p)
{
if (p & 1) res *= x, res %= mod;
x *= x, x %= mod;
p >>= 1;
}
return res;
}
void init()
{
fac[0] = ifc[0] = 1;
for (int i = 1; i < nr << 1; i++) fac[i] = fac[i - 1] * i % mod;
ifc[(nr << 1) - 1] = qpow(fac[(nr << 1) - 1], mod - 2);
for (int i = (nr << 1) - 2; i >= 1; i--) ifc[i] = ifc[i + 1] * (i + 1) % mod;
}
int C(int x, int y)
{
if (x < 0 || y < 0 || x < y) return 0;
return fac[x] * ifc[y] % mod * ifc[x - y] % mod;
}
bitset<nr> b, base;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
init();
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], up = max(up, a[i]), base.set(a[i]);
int res = 0;
for (int i = 0, now, sum = 0; i <= n; i++)
now = C(n, i), (i > 1 ? res += now * sum % mod, res %= mod : 0), sum += now, sum %= mod;
for (int d = 1; d <= up; d++)
{
b = base;
for (int i = d; i <= up; i += d)
if (base[i])
{
b &= b << d;
int cnt = b.count();
if (!cnt) break; res += mod - cnt, res %= mod;
}
else break;
}
for (int d = 1; d <= up; d++)
for (int i = d, cnt = 0, lst = 0, tot = 0, flag = 1; i <= up; i += d)
{
base[i] ? (cnt++, lst++) : (flag = 0, lst = 0), tot += flag;
if (i + d <= up && base[i] && base[i + d])
{
res += mod - C((cnt << 1) - 1, cnt - 1), res %= mod;
if (cnt > 1) res += C((cnt << 1) - 1, cnt - 2), res %= mod;
res += min(tot, lst), res %= mod;
}
}
cout << res << '\n';
return 0;
}
```