自动搬运

查看原文

来自洛谷，原作者为

	xhabc66 失去人性，失去很多；失去兽性，失去一切。|| 不上紫名不划掉（永远搞不掉了吧）|| 没有金钩不划掉

搬运于2025-08-24 22:54:05，当前版本为作者最后更新于2022-07-13 16:24:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\texttt{Subtask 0}$

爆搜。或者直接输出 $m$。

$\texttt{Subtask 0.5}$

设 $a_i$ 为最终赢到 $i$ 澳元的方案数，$c_i$ 表示是否有面值为 $i$ 的筹码（有为 $1$，没有为 $0$），则 $a_n$ 为答案。

递推式：

$$a_1=c_1$$ $$a_{i+1}=(a_{\lceil\frac{i+1}{2}\rceil}+\ldots+a_{i-1}+a_i)+c_{i+1} $$

时间 / 空间复杂度为 $O(n^2+m)/O(n+m)$。

$\texttt{Subtask 1}$

设 $b_i$ 为 $a_i$ 的前缀和（$b_1=a_1$，$b_i=b_{i-1}+a_i$），注意到 $\lceil\dfrac{i+1}{2}\rceil=\lfloor\dfrac{i}{2}\rfloor+1$，则 $b_n-b_{n-1}$ 为答案。

$$b_1=c_1$$ $$b_{i+1}=(b_i+b_i-b_{\lfloor\frac{i}{2}\rfloor})+c_{i+1} $$

时间 / 空间复杂度为 $O(n+m)/O(n+m)$。

$\texttt{Subtask 2}$

不难发现，求 $b_{i+1}$ 时只需要 $b_i$ 及 $b_{\lfloor\frac{i}{2}\rfloor}$ 的值。于是，我们可以每次只存 $b_i,b_{\lfloor\frac{i}{2}\rfloor},b_{\lfloor\frac{i}{4}\rfloor},b_{\lfloor\frac{i}{8}\rfloor},\ldots,b_1$ 的值。例如：

$i$	存储的下标
$1$
$2$	$2,1$
$3$	$3,1$
$4$	$4,2,1$
$5$	$5,2,1$
$6$	$6,3,1$
$7$	$7,3,1$
$8$	$8,4,2,1$
$\ldots$

不难发现，每次从右往前更新即可。时间 / 空间复杂度为 $O(n+m)/O(m+ \log n)$。

参考代码（std）

#include <bits/stdc++.h>
using namespace std;
const int B = 32, P = 1e9 + 7, M = 1e6 + 5;
int b[B], p[B], a[M];
int main()
{
    int n, m, s = 0;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        int t = i & (-i);
        for (int j = 1, k = 1, l = i; k <= t; j++, k <<= 1, l >>= 1)
        {
            b[j] <<= 1;
            b[j] -= b[j + 1];
            if (p[j] != m && a[p[j] + 1] == l) b[j]++, p[j]++;
            b[j] %= P;
            if (b[j] < 0) b[j] += P;
        }
        if (i == n - 1) s -= b[1];
        if (i == n) s += b[1];
    }
    cout << (s % P + P) % P;
    return 0;
}