题目：[[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$，求 $\cfrac{\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{cases}i&\text{if}~i\le 2\\f_{i-1}+f_{i-2}&\text{else}\end{cases}$，对于任意一个正整数 $x$，可以将其分解成唯一的 $\sum\limits_{i=1}^{k}f_{a_k}$ 的形式，设 $f(x)=\operatorname{\oplus}\limits_{i=1}^kf_{a_k}$，给你 $T$ 组数据，每组数据为 $(l,r)$ 的形式，求 $\operatorname{\oplus}\limits_{i=l}^rf(i)$。 --- 首先，对于一个数 $x$，我们需要考虑对它的分解。经过好渴鹅的深思熟虑，可以发现令最大的 $k$ 使得 $f_k\le x$，那么 $x$ 的分解里面必定会有 $f_k$。 现在我们需要求 $\sum\limits_{i=l}^r f(i)$。通过差分，可以将其转化为 $\sum\limits_{i=1}^r f(i)-\sum\limits_{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$，也就是可以输出的答案最多是这个数。 令 $dp_j$ 设为能否凑出 $j$ 的金额，那么对于任意的 $i$，我们可以使用 $a_i$ 的金额来不足，即 $dp_j\gets dp_j \operatorname{or} dp_{j-a_i}$。最后找到最大的 $j$，使得 $dp_j=0$，输出这个 $j$ 就行了。 炸裂的是，这个原本应该 $30$ 分的代码最后得了 $70$ 分。 ## 总结 - **排名**：$1$； - **比赛分数**：${} 370/400 {}$； - **情况**：超预期； - **问题**：不会同余最短路。