FAOI-R2【B】A trip to Macao 题解

· · 题解

\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 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 \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;
}