0301测试
0301测试
T1
考虑如何检查一个条件是否合法，如果最高位为任意，那么两边需要都合法，否则要求两边至少有一个合法。
考虑两边的检查，发现第 \(i\) 层的节点个数为 \(2^i\)，总的情况数为 \(2^{n-i}\)，因此可以记忆化搜索一下。用一个 \(mask\) 的前若干位表示限制，后若干位表示高位的数字即可。
也可以这样想：考虑算所有的情况，设 \(T(n)\) 表示计算第 \(n\) 层所有情况的复杂度，暴力计算有 \(T(n)=2^n+4T(n-1)=2^{2n}\)，实际上发现对于只有第 \(n\) 层不同的情况可以只算一次，于是 \(T(n)=2^n+2T(n-1)\)，得到 \(T(n)=n2^n\)。
T2
做法一
考虑钦定 \(A\) 组先选满，枚举 \(A\) 组选满的位置计算对应概率然后再乘二。对于每一个位置 \(p\)，基本情况总数为 \(\binom{p-1}{n-1}\)，每种基本情况等概率取到，概率为 \(2^{-p}\)，分三类讨论
如果 \(x_k<p\)，那么 \(k\) 个人既可以在 \(A\) 组也可以在 \(B\) 组，对应的基本情况数分别为 \(\binom{p-1-k}{n-1-k}+\binom{p-1-k}{n-1}\)。
如果 \(x_k=p\)，那么一共有 \(\binom{p-k}{n-k}\) 种基本情况。
如果 \(x_k>p\)，首先 \(p\notin X\)，然后记 \(c\) 为 \(p\) 之前的 \(x\) 个数，基本情况总数为 \(\binom{p-1-c}{n-1}\)。
于是有一个 \(nq\) 的做法。
观察到查询的答案是一个二元函数 \(f(p,x)\) ，对于 \(x\) 较小的情况可以预处理前缀和，对于 \(x\) 较大的情况，查询数比较少，可以暴力。于是有一个 \(n\sqrt q\) 的做法。
进一步观察，\(2^{-p}\binom{p-1-c}{n-1}\) 可以很容易的预处理 \(2^{-p}\binom{p-1}{n-1}\) 的前缀和然后查询时乘上一个 \(2^{-c}\)。
对于 \(2^{-p}\binom{p-1-k}{n-1-k}\)，答案应该是： \[ \begin{align} \sum_{p=x_k+1}^{2n-1}2^{-p}\binom{p-1-k}{n-1-k}&=\sum_{p=\max(n,x_k+1)}^{2n-1}2^{-p}\binom{p-1-k}{n-1-k}\\ &=\sum_{p=\max(n,x_k+1)}^{2n-1}2^{-p}\binom{p-1-k}{n-p}\\ &=\sum_{p=\max(n,x_k+1)-k-1}^{2n-1-k-1}2^{-p-k-1}\binom{p}{n-k-1}\\ \end{align} \] 注意到 \(\sum k\) 其实很小。
好吧，我不会线性做法，摆了。
做法二
先只算都在 \(A\) 组的情况，然后分 \(B\) 选满的位置 \(p\) 所在的区间讨论。
\(p>x_k\)：令 \(x_k\) 及之前每一种可能的硬币选择为基本情况，需要计算在 \(x_k\) 处 \(X\) 都取到 \(A\) 且 \(B\) 不能被选满的方案总数，隐含条件是 \(x_k\) 之前 \(A\) 也不能被选满。
可以暴力的算组合数，枚举剩下的 \(x_k-k\) 个数有多少个分配到 \(A\) 中，可以直接限制 \(A,B\) 都满足要求，即 \(\sum\limits_{i=\max(0,x_k-k-n+1)}^{n-k}\binom{x_k-k}{i}\)。
然后 \(\sum k\) 是比较小的，于是放宽一下限制，算 \(\sum\limits_{i=\max(0,x_k-k-n+1)}^{n}\binom{x_k-k}{i}\) 再减掉，容易发现这个式子只和 \(x_k-k\) 有关，而这个式子本身也不是很难算，进一步的将 \(\max\) 的限制去掉，变成 \(\sum\limits_{i=0}^n \binom{x}{i}\)，然后对于 \(x-n\ge0\) 的情况，需要减去 \(\sum\limits_{i=0}^{x-n}\binom{x}{i}\)。都可以拆组合数然后动态规划。 \[ \begin{align} \sum\limits_{i=0}^{x-n}\binom{x}{i}&=\binom{x-1}{0}+\sum\limits_{i=1}^{x-n}\binom{x-1}{i-1}+\binom{x-1}{i}\\ &=\binom{x-1}{0}+\sum_{i=1}^{x-n}\binom{x-1}{i}+\sum_{i=1}^{x-n}\binom{x-1}{i-1}\\ &=\binom{x-1}{x-n}+\sum_{i=0}^{x-n-1}\binom{x-1}{i}+\sum_{i=0}^{x-n-1}\binom{x-1}{i}\\ &=\binom{x-1}{x-n}+2\sum_{i=0}^{x-1-n}\binom{x-1}{i} \end{align} \]
另一种考虑方式是算一个 \(f_w\) 表示一共 \(w\) 个，\(A,B\) 都不超过的情况总数，然后需要减去 \(B\) 抵到的情况数，然后又因为需要把 \(A\) 超过的情况去掉，\(A\) 超过是因为 \(k\) 个被塞进了 \(A\)，分别枚举超过 \(1,2,3\cdots k\) 个减掉对应的基本情况数即可。\(f_w\) 的转移考虑直接放 \(A,B\) 然后去掉不合法的情况。
\(x_{i-1}<p<x_{i},i\in[1,k]\)
将基本情况定为 \(x_i\) 之前（不含）的硬币状态，限制有两个，\(|B|\) 不小于 \(n\)，且 \(X\) 内的是必须为 \(A\) 的。满足 \(A\) 限制的总情况数为 \(2^{x_i-i}\)。满足 \(A\) 限制但不满足 \(B\) 限制的情况数为 \(\sum\limits_{i=0}^{n-1}\binom{x_i-i}{i}\)，先扣掉。这里不需要考虑 \(A\) 被选满，因为 \(A\) 被选满的情况确实应该扣掉。然后再减去再 \(x_{i-1}\) 之前就满足 \(B\) 限制的所有情况，注意额外带一个 \(2_{x_i-x_{i-1}-1}\) 的系数。
这里还会有一些误解，其实隐含了 \(|A|<n\) 的限制，实际上如果这两个限制都满足那么这个隐含限制一定满足，因此不管这个隐含限制直接算也是可以的。
当使用容斥计算 "恰好" 时，应该减掉上一次的 "至少" 而不是 "恰好"，记录 \(lst\) 的时候要注意。
T3
先考虑构造一种合法的解满足条件。挨个确定值的办法并不好弄。考虑先确定前 \(i\) 个的大小关系，如果前 \(i\) 个合法了，并且第 \(i+1\) 个可以放到一个位置，满足前面没有不小于 \(a_{i+1}\) 且存在至少一个 \(a_{i+1}-1\)，那么就合法。于是得到一个有解的充要条件：任何一个前缀 \(a_i\) 值的集合连续。
现在考虑算 \(i\) 位置的答案，它前面的不小于它的元素必须在它后面，它后面的元素可以线性扫一遍，维护前缀连续最大值算出来。
考虑优化，对于一个 \(i\) 算答案的时候，就是要找到依赖它以及它前面不小于它的元素的所有元素。后面的比 \(a_i\) 大的元素如果能在 \(i\) 之后找到一个 \(a_i\) 依赖，那么就可以被放在 \(i\) 前面。
元素的依赖关系好像是构成一棵树的，于是建树，每个元素向它的第一个前驱连边，然后 \(i\) 节点以及它同层左边的兄弟里所有节点都不能放在 \(i\) 前面，于是算出了 \(p_i\) 的最大值。