题解

honglan0301 · 2024-04-03 15:26:44 · 个人记录

T1

首先关于“连续段”有个非常典的扫描线+维护区间最小值个数/权值和的套路（CF997E），在此我们直接使用。

考虑容斥，先仅考虑交长度 r'-l'+1\geq k 的限制做一遍，再把是包含关系的区间对减掉。以下分别计算。

求 r'-l'+1\geq k 的连续段对 (l_1,r_1),(l_2,r_2) 数量：

考虑枚举 l'，那么一对连续段 (l_1,r_1),(l_2,r_2) 满足条件当且仅当 l_1= l',r_1\geq l'+k-1,l_2\leq l',r_2\geq l'+k-1。
发现两个区间限制独立。于是根据乘法原理，显然可以分别求出 (l_1,r_1) 与 (l_2,r_2) 的方案数再乘起来。使用套路后两者均是简单扫描线问题，使用支持“区间加减，求区间最小值个数/区间历史版本最小值个数”的线段树即可。

求 l_1\leq l_2\leq r_2\leq r_1,r_2-l_2+1\geq k 的连续段对 (l_1,r_1),(l_2,r_2) 数量：

考虑枚举 l_2，这样 k 的限制仅与 (l_2,r_2) 有关。
同样进行扫描线，维护历史版本最小值个数。发现对于一个 l_2，我们即要求出 [l_2+k-1,n] 中每个最小值对应的后缀历史版本最小值个数之和，你发现它也可以用线段树维护，做完了。

总时间复杂度 O(n\log n)。

*事实上，有个优秀性质是 l_1\leq l_2\leq r_1\leq r_2 时，[l_1,l_2-1],[l_2,r_1],[r_1+1,r_2] 都是连续段，于是据此有简单得多的写法。

std（？）

简单做法

T2

一：判定

容易发现 n\times m=nm，于是 S 合法即要求可以通过平移和叠加两种操作使得 S 不重不漏地覆盖 1\sim nm 中的所有元素，于是若 T 存在则 T 唯一，于是我们学会了如何判定其合法性：

判定方法：首先把集合 S 转为 01 串 s，其中规定 s_i=1 当且仅当 i\in S。然后我们定义一个空串 s'，那么 T 可以通过重复进行“找到下标最小的 s'_k=0，把 k-1 加入 T ，并令每个 s'_i\gets s'_i\operatorname{or}s_{i-k}”这一操作来得到。若最终恰进行 m 次操作则 S 合法。

接下来考虑观察结论，进行优化：

【结论 0】：合法串 s 中至少有一个 1（根据定义可知 s_1=1）。
【结论 1.1】：记串中所有“全 1 连续段”分别是 [w_1,w_1+l_{1}-1],[w_2,w_2+l_2-1],\dots,[w_c+l_c-1]。那么合法串 s 中 l_1=l_2=\dots=l_c。

*证明：我们假设 l_1=k（即 s_1 所在的连续段长为 k），那么

① 显然有 k\in T，因此这保证了 \forall len_i\leq k，否则在较长连续段处会出现重叠。

② 显然有 \{1,2,\dots,k-1\}\bigcap T=\emptyset，因此若 \forall i\leq i_0,len_i\geq k 成立，则 len_{i_0+1}\geq k，否则 s_{w_{i_0+1}+k-1} 无法被 1 覆盖。于是归纳得到 \forall len_i\geq k。

③ 综上，\forall len_i=k。
【结论 1.2】：记串中所有"全 0 连续段"分别是 [z_1,z_1+r_1-1],[z_2,z_2+r_2-1],\dots,[z_d,z_d+r_d-1]。那么合法串中 k\mid \gcd\{r_i\}。

*证明：由于 len_i\equiv k，每个全 0 段都由若干个长为 k 的全 1 段不重不漏地填充而成，那么其长度 r_i 必然是 k 的倍数。
【结论 1.3】：当 k>1 时，串 s 合法当且仅当串 s'=s_1s_{k+1}\dots s_{|s|-k+1} 合法（|s'|=\frac{|s|}k{}，后者是 k=1 且更短的串）。

*证明：充分性显然；而显然 \forall i\in T,k\mid i，因此取 T'=\{x\mid kx\in T\}，易知 (S',T') 满足条件，因此必要性得证。
【结论 2.1】：当 k=1 时（每个全 1 连续段有且仅有一个 1 时），记 w_2-w_1=p，则合法串 s 中 \forall i, p\mid |w_i-w_{i-1}|

*证明：显然 \{0,1,\dots,p-1\}\subset T，接下来可以归纳证明向 T 中放入的数是若干个长为 p 的连续段，因为每轮 w_1 和 w_2 都会填进同一个全 0 段中，于是 \forall i,p\mid w_i-w_{i-1}。
【结论 2.2】当 k=1 时，串 s 合法当且仅当串 s'=s_1s_{p+1}\dots_{|s|-p+1} 合法（|s'|=\frac{|s|}{p}，后者是 k\neq 1 且更短的串）

*证明同 1.3。

于是综上，我们发现合法串 s 总可以通过交替进行结论 1/2 中的缩串操作最终变为 1。

二：转化

将“缩串”过程反向考虑，那么合法串的数量即从 s=1 开始不断交替进行扩串所能得到的 |s|=nm，cnt_1=n 的不同串数量。我们记 (x,y) 表示串中 1 的数量与串长的二元组，可以发现两种操作分别是：

1.\ (x,y)\rightarrow (k_1x,k_1y)

2.\ (x,y)\rightarrow (x,k_2y)

其中要求 k_1,k_2>1。同时易知，当两种操作交替进行时，两个不同的操作序列总是对应了不同的结果串，因此对合法操作序列计数即可。我们对操作 1,2 分别计算，只需解决以下问题：

对于每个 i ，对于长为 i，使得 \prod\limits_{j=1}^ik_j=n 且 \forall k_i>1 的序列 k 计数。

而由于 n,m 都由唯一分解形式给出，我们最终获得如下子问题（p_i 的具体值不影响答案）：

有 n 种球，第 i 种球有 x_i 个，相同种类的球不做区分，对于每个 1\leq m\leq \sum x_i 求出将这些球放到 m 个不同的盒子里，且每个盒子都非空的方案数。

三：最终做法

首先考虑二项式反演，记 f_{i,j} 表示把球放到 i 个盒子里，钦定有 i-j 个盒子为空的方案数，那么根据简单插板法有：

f_{i,0}=\prod C_{i+a_i-1}^{i-1}

f_{i,j}=f_{j,0}\times C_{i}^j

而恰好有 0 个盒子为空的方案数 g_i 显然是：

g_i=\sum f_{i,j}\times (-1)^{i-j}=\sum f_{j,0}\times C_{i}^j\times (-1)^{i-j}

记 \sum x_i=D，时间复杂度 O(D^2)，考虑以下两点优化。

本质不同的 a_i 只有 O(\sqrt D) 种，于是对每种 a_i 的贡献快速幂，f_{i,0}=\prod (C_{i+j-1}^j)^{cnt_j}，由于 \sum j\times cnt_j=D，时间复杂度 O(D\sum \log cnt_j)=O(D\sqrt D)。
求 g_i 时使用 NTT 优化。具体地，把 g_i 与 f_{i,0} 的 EGF G(x) 和 F(x) 写出，那么有 G(x)=F(x)\times H(x)，其中 [x^i]H(x)=\dfrac{(-1)^i}{i!}，时间复杂度 O(D\log D)。

综上，在 O(D\sqrt D) 的时间复杂度内解决了问题。

std by 原出题人

T3

原：UR #22 T3，以下为原题题解。我们记 goodier 为小 A，xsap 为小 B。

一：sub 1（a=0）

当 p=0 时，小 B 永远不会选择翻转。因此当且仅当初始硬币全为正面，答案为 0；否则小 A 也一直不操作即可保证游戏不结束，答案为 -1。

二：sub 2

当 p=1 时，小 B 每次都会选择翻转背面向上的硬币。

我们把同色的连续一些硬币称为一段。对于段数大于

- 当局面为全 0 或全 1，小 B 显然获胜。 - 当局面为 00...011...1 时，小 B 也显然获胜。 - 当局面为 11...100...0 时，小 B 能否获胜与 1 的个数有关。当仅有一个 1 时，不管小 A 如何操作，都会变为上述小 B 必胜局面。否则，小 A 不翻转第一个 1 ，即可使段数大于 2，那么游戏不会结束，答案为 -1。 - 否则，初始段数大于 $2$，小 A 每次都选择翻转，答案为 -1。三：sub 3 考虑状压 dp。状态总数 $O(2^n)$，其中我们称 $c_x$ 表示最左侧硬币的状态；称 $trans_{i,0/1}$ 表示去掉状态 $i$ 最左边的硬币，并在右侧新增一个背面/正面朝上的硬币所对应的状态，那么转移形如：若 $c_x=1$ ， $f_x=\max(f_{trans_{x,0}},f_{trans_{x,1}})+1$，若 $c_x=0$， $f_x=pf_{trans_{x,1}}+(1-p)f_{trans_{x,0}}+1$。这是个带环还带 $\max$ 的 dp，我们枚举 $\max$ 取值来源，每次用高斯消元求解。特判掉 $p=1$ 或 $p=0$ 的情况之后若出现矩阵不满秩的情况则一定不合法。另外若求出的dp值不满足上述约束则也不合法。可以证明最多只有一种情况合法（因为最优策略唯一）。若没有合法情况输出 -1 ，否则输出唯一合法的解即可。注意求解需先用 double 算出最优策略再算出取模后的答案。复杂度为 $O(2^{2^{n-1}}\cdot2^{3n})$。四：sub 4 为了进一步挖掘性质优化算法，先来研究一下两人都使用最优策略时的这个博弈问题（假设小 B 希望最小化步数，小 A 希望最大化步数）。考虑到全正的局面是已知的最终局面，我们从这个局面开始推出其他局面的最优步数。具体地，我们类似“过河卒”地倒序 bfs，维护一个队列，其中存储一些已知最优步数且等待扩展的局面。我们每次从队头取出一个已经确定最优步数的局面 $z$ ，考察有哪些局面能一步转移到它，设为 $x,y$，其中 $c_x=0,c_y=1$。则如果 $x$ 是第一次被访问到，则 $x$ 的最优决策即可转移到 $z$。（小 B 希望最小化步数）。类似的，如果 $y$ 是第二次被访问到，则 $y$ 的最优决策转移到 $z$。（小 A 希望最大化步数）被扩展到的新局面存到队尾即可。注意这里的 $x$ 和 $y$ 只有第一个硬币不同。则可以发现 $x$ 和 $y$ 总是同时被访问到，它们要么都是第一次，要么都是第二次。于是每次都有且仅有一个局面可以扩展。那么在一种理想的情况下，局面之间的转移关系就构成了一条链，所有局面的最优步数恰好取遍了 $0$ 到 $2^n-1$ 。但是还有一个例外：当全正局面作为第二次访问到的 $y$ 出现时，它已经无法再被扩展了。此时还没有被扩展到的局面就是无解局面：以它们为初始局面的游戏无法结束。选手们当然可以验证出在给定的数据范围内不存在这种例外情况。就算没有得到这个结论，也可以在代码中特判。当存在无解局面时，不管初始局面是否无解直接输出 -1 即可，这是因为在小 B 随机的游走的时候，总会有可能走到无解局面。下面还是证明一下在 $n$ 取任何值时都不会存在上述例外发生。即对于任何初始局面，小 B 有必胜策略。证明：我们把初始局面的硬币按 $1$ 到 $n$ 标号。从硬币按 $1$ 到 $n$ 排列到下一次硬币按 $1$ 到 $n$ 排列的一次过程称为一回合。对于每一回合，起初小 B 看到背面的硬币就翻面，直到小 A 第一次操作，小 B 在这一回合之后就都不操作。这样会发现每一轮过后局面表示的二进制数都会变小。直到变成全 0，此时小 B 一路翻过去就获胜了。证毕。注意，上面的这个策略只是保证获胜的策略，并不是步数最少的策略。于是，得到了这样的结论：局面之间的转移关系构成了一条链，所有局面的最优步数恰好取遍了 $0$ 到 $2^n-1$ 。我们可以按局面在这条链上的位置来给局面编号，局面 $i$ 的最优步数为 $i$，以下均使用这个标号描述局面。回到最初的问题。当小 B 操作与否随机时，利用这个结论来优化一下算法。对于小 A，他从 $i$ 要么到 $i-1$，要么到某个 $x(x < i-1)$。对于小 B，他从 $i$ 要么到 $i-1$，要么到某个 $y(y > i-1)$。下面证明小 A 每次都从 $i$ 到 $i-1$，即期望 $f_i$ 单调递增。反证，若 $x < y,f_x > f_y$，则从 $y$ 到第一次到达 $x$ 的这些回合里，小 A 都从 $i$ 走到 $i-1$，那么必定经过 $x$。第一次到达 $x$ 之后按之前的最优策略走。则 $f'_y > f_x > f_y$，与最优性矛盾。则 $f_i$ 单调得证。于是我们去掉了转移方程中的 $\max$，可以高斯消元解决，而观察方程组形态可以优化到 $O(2^{2n})$。五：sub 5 观察到从局面 $i$ 一定会经过局面 $i-1$。我们改变状态定义：从 $i$ 到 $i-1$ 的期望步数。写出方程发现可以按链的顺序递推，优化为 $O(2^n)$。