【题解】2021牛客OI赛前集训营-提高组（第七场）精

UPD: std 链接

A https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49033117
B https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49033126
C https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49033140
D https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49033129

依依寺

我们考虑先后手的策略， ${0}$ 的作用仅仅是改变后续操作的奇偶性，因此 ${0}$ 的个数 $a$ 可以对 ${2}$ 取模。

接下来，我们先不考虑 ${0}$ 的存在。

先手取了 ${1}$ 之后，后手必定取 ${1}$ ，然后先后手依次是 ${2,1,2,1,2,1\cdots}$ ；

先手取了 $2$ 之后，后手必定取 $2$ ，然后先后手依次是 ${1,2,1,2,1,2\cdots}$ 。

综上，观察到取的方式一定是 $1,2$ 交替（除了开头）。

有额外一个 $0$ 即可以调控上述的某次操作的先后手关系，分类讨论即可。

当然，此类博弈题一个比较合适的方式是打表找规律。

时间复杂度 $\mathcal O(T)$ 。

武义寺

设该数列最早在 $i$ 位置出现 $i>a[i]$ ，令 $k=n+1-i$ ，枚举 $a_i=j$ ，则前 $i-1$ 个数的可行的方案为

$\sum\limits_{j=1}^{i-1} (k+1)^{i-1-j}k^j=(k+1)^{n-k}\times \frac{k}{k+1}\times \sum\limits_{j=0}^{n-k-1}(\frac{k}{k+1})^j=k((k+1)^{n-k}-k^{n-k})$

因此答案为：

$\sum\limits_{k=1}^{n} (n+1-k)\times k((k+1)^{n-k}-k^{n-k})\times (k-1)! = \sum\limits_{k=1}^{n}(n+1-k)\times k!\times ((k+1)^{n-k}-k^{n-k})$

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

依久依久

首先，求 $\oplus_{i=l}^{r} \text{val}(i)$ 可以转化为求前缀异或和 $S(n)=\oplus_{i=1}^{n}\text{val}(i)$ ，那么答案就是 $S(r) \oplus S(l-1)$ 。

我们考虑递归的求 $S(n)$ ，即找到最大的一个 $k$ 满足 $fib_k\le n$ ，那么

$S(n)=S(fib_k-1)\oplus S(n-fib_k)\oplus \begin{cases}fib_k \ \text{if } n-fib_k+1 \text{ is odd} \\ 0 \ \text{otherwise}\end{cases}$

找到这个 $k$ 可以在预处理的 $fib$ 数列上二分。

注意到斐波那契数列和 ${2}$ 的幂次类似，递归执行只会访问到 $\mathcal O(\log 值域)$ 种 ${n}$ ，故记忆化搜索即可。

时间复杂度 $\mathcal O(T\log 值域\log\log 值域)$ 。

补幺梨

对于 $n,m$ 较小的情况，猜测最大不能被表示的数不太大，那么就可以直接跑完全背包，用 bitset 优化。

不妨假设 $k = \min\limits_{i=1}^{n} a_i$ ，对于模 $k$ 跑同余最短路， $dis[i]$ 表示最小的模 $k=i$ 的数，则 $dis[i]+ki$ 均可被表示出来（不停加入 $k$ ），因此答案就是 $\min\limits_{i=0}^{k-1}\left(dis_i-k\right)$ 。