2024.9.23 模拟赛

题目：2024.9.23 题目

依依寺

有 $n=a+b+c$ 个数，现在有两个人在轮流选数，无数可选或选了之后选择的数的和为 $3$ 的倍数的人输，两人都使用最佳策略，问你哪个人能赢。

---

首先，这道题里面的 $0$ 起到的是交换双方的作用，也就是说，这一步我不出等同于下一步你出的就是我出的，因此当 $0$ 的数量为偶数时，它完全没有作用；只有当 $0$ 的数量为偶数时，它才会交换双方。

其次，由于两个人都会按照最优方式取数，因此我们只需要思考它们最多能够持续多久。经过「短暂」的思考后，我们可以想到，一共两种方式：$1,1,2,1,2,\cdots$ 或者是 $2,2,1,2,1,\cdots$。因此答案就显而易见了，我们只需要求出最后一个出牌的人是谁，那个人就是胜者。时间复杂度 $\mathcal{O}(T)$。

武义寺

给定 $n$，令 $f(p)$ 等于最小的 $i$ 满足 $1\le i\le n,a_i<i$。对于长度为 $n$ 的 $n!$ 个排列 $p$，求 $\frac{\sum f(p)}{n!}$。

---

我们枚举 $f(p)$ 的答案为 $i$，那么 $i$ 必须 $a_i<i$ 且对于任意 $j<i$ 必须 $p_j\le j$。我们枚举 $j$ 使得 $a_i=j$，令 $k=n-i+1$，然后考虑前 $i-1$ 个数又多少种选择。

由于我们已经在位置 $i$ 填上了 $j$，因此位置 $i-1$ 可以选择 $k+1$ 个数，位置 $i-2$ 也能选择 $k+1$ 个数（有一个数被 $i-1$ 占了）。一直到位置 $j$，这是我们突然发现不能选已经被选过的 $j$ 了，因此它和它前面的数都只能选 $k$ 个。因此，前 $i-1$ 个数的方案数为：

$$\sum _{j=1}^{i-1}(k+1{)}^{i-j-1}\times k^j=k\times \left[(k+1{)}^{n-k}-k^{n-k}\right]$$

此时答案已经于 $i$ 没有关系了，因此我们可以只枚举 $k$。接下来我们枚举 $i$，通过简化，我们可以得到最终的和为：

$$\sum _{k=1}^{n}i!\times (n-i+1)\times \left[(k+1{)}^{n-k}-k^{n-k}\right]$$

由于题目当中要求我们求期望，并且我们没有考虑答案为 $n+1$ 的特殊情况，因此我们需要将这个和加上 $n+1$ 之后除以 $n$。另外，题目当中要进行有理数取余，可以使用快速幂法求得。时间复杂度为 $\mathcal{O}(n{\log }_{2}m)$（$m$ 为模数）。

依久依久

令 $f_i=\{\begin{array}{ll}i& \text{if}i\le 2\\ f_{i-1}+f_{i-2}& \text{else}\end{array}$，对于任意一个正整数 $x$，可以将其分解成唯一的 $\sum _{i=1}^k{f}_{a_k}$ 的形式，设 $f(x)={\oplus }_{i=1}^k{f}_{a_k}$，给你 $T$ 组数据，每组数据为 $(l,r)$ 的形式，求 ${\oplus }_{i=l}^{r}f(i)$。

---

首先，对于一个数 $x$，我们需要考虑对它的分解。经过好渴鹅的深思熟虑，可以发现令最大的 $k$ 使得 $f_k\le x$，那么 $x$ 的分解里面必定会有 $f_k$。

现在我们需要求 $\sum _{i=l}^{r}f(i)$。通过差分，可以将其转化为 $\sum _{i=1}^{r}f(i)-\sum _{i=1}^{l-1}f(i)$。我们可以使用一个函数 $S(n)$ 来求这个数。我们知道，两个相同的数进行异或，结果为 $0$；而 $0$ 跟任意数异或结果就是那个数。因此对于 $n$，我们同样找到一个最大的 $k$ 使得 $f_k\le n$，然后此时会有 $f_k\sim n$ 这 $n-f_k+1$ 个数会取到 $f_k$，我们只需要判断一下奇偶性就行了（奇数时额外异或 $f_k$）。然后对于这些可以取到 $f_k$ 的数，它们通通减掉了 $f_k$，因此答案需要异或上 $S(n-f_k)$。其它没有取到 $f_k$ 的数，需要继续进行计算，因此答案需要异或上 $S(f_k-1)$。

也可以直接求 $l\sim r$ 的和，但是代码会复杂一点，思路几乎一样。

由于斐波那契数列的第 $84$ 项是最大的小于 $1\times 10^{18}$ 的数，因此令 $m=10^{18}$，该算法的时间复杂度为 $\mathcal{O}(m\log m)$。

补幺梨

有 $n$ 种纸币，每种纸币无数张，最大面额不超过 $m$，第 $i$ 种纸币面额为 $a_i$，现求一最大值 $x$，使得无法使用这 $n$ 种纸币拼凑出 $x$。

---

好渴鹅不会这道题目，所以使用的是完全背包来找最小值（正解是同余最短路）。鹅的目标是骗够 $30$ 分，因此时间复杂度为 $\mathcal{O}(nm)$ 的完全背包中的 $m$ 最大可以到达 $1\times 10^5$，也就是可以输出的答案最多是这个数。

令 $d{p}_j$ 设为能否凑出 $j$ 的金额，那么对于任意的 $i$，我们可以使用 $a_i$ 的金额来不足，即 $d{p}_j\leftarrow d{p}_j\mathrm{or}d{p}_{j-a_i}$。最后找到最大的 $j$，使得 $d{p}_j=0$，输出这个 $j$ 就行了。

炸裂的是，这个原本应该 $30$ 分的代码最后得了 $70$ 分。

总结

• 排名：$1$；
• 比赛分数：$370/400$；
• 情况：超预期；
• 问题：不会同余最短路。