P17747 题解

· · 题解

该题解为本题的官方题解。

报数 x 后，下一个可报的数必须不小于 \lfloor \sqrt{x} \rfloor + 1，不大于 x - 1。

设 f(x) 表示从 x 开始报数的方法数量，则：

f(x) = \begin{cases} 1 & x = 2 \\ \sum_{y = \lfloor \sqrt{x} \rfloor + 1}^{x - 1} f(y) & x \ge 3 \end{cases}

直接计算这个求和表达式，时间复杂度会达到 \mathcal{O}(x^2)，无法通过。

不妨设 g(x) = \sum_{y=2}^{x} f(y) 为 f 的前缀和，则当 x \ge 4 时，f(x) = g(x - 1) - g(\lfloor \sqrt{x} \rfloor)。

但是这样计算，时间复杂度仍有 \mathcal{O}(x)，在 x \le 10^{12} 限制下仍无法通过。

考虑在每个完全平方数处将数轴切割成片段。

容易看出，当 q \ge 2，0 \le r < (q+1)^2 - q^2 时，q^2 \le q^2 + r < (q+1)^2，因此 \lfloor \sqrt{q^2 + r} \rfloor = q。

于是可以证明，当 q \ge 2，0 \le r < (q+1)^2 - q^2 时，f(q^2 + r) = 2^r \cdot f(q^2)。

下面用归纳法证明：

\begin{array}{l} f(q^2 + r) = g(q^2 + r - 1) - g(\lfloor \sqrt{q^2 + r} \rfloor) \\ \phantom{f(q^2 + r)} = g(q^2 + r - 1) - g(q) \\ \phantom{f(q^2 + r)} = g(q^2 + r - 2) - g(q) + f(q^2 + r - 1) \\ \phantom{f(q^2 + r)} = g(q^2 + r - 2) - g(\lfloor \sqrt{q^2 + r - 1} \rfloor) + f(q^2 + r - 1) \\ \phantom{f(q^2 + r)} = 2f(q^2 + r - 1) \\ \phantom{f(q^2 + r)} = 2^r \cdot f(q^2) \end{array}

证毕。

于是，可以简化以上表达式。创建数列 a 和 b，使得 a_q = f(q^2)，b_q = g(q^2)。于是，f(x) 的表达式可以改成：

f(x) = \begin{cases} 1 & x = 2, 3 \\ a_{\lfloor \sqrt{x} \rfloor} \cdot 2^{x - \lfloor \sqrt{x} \rfloor^2} & x \ge 4 \end{cases}

由 \sum_{y=1}^{r} 2^y = 2^{r+1} - 2，故 g(x) 的表达式可以改成：

g(x) = \begin{cases} 1 & x = 2 \\ 3 & x = 3 \\ b_{\lfloor \sqrt{x} \rfloor} + a_{\lfloor \sqrt{x} \rfloor} \cdot (2^{x - \lfloor \sqrt{x} \rfloor^2 + 1} - 2) & x \ge 4 \end{cases}

数列 a 和 b 可以用公式 a_q = g(q^2 - 1) - g(q)，b_q = g(q^2 - 1) + a_q 递推得出，从 2 递推到 \lfloor \sqrt{x} \rfloor 即可，从而 f(x) 即为答案。别忘了输出时取模。

代码如下：

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
const LL MOD = 1'000'000'007;

LL sq(LL x)
{
    return x * x;
}

LL isqrt(LL x)
{
    return (LL)floor(sqrt(x));
}

LL pow_mod(LL base, LL exp)
{
    LL result = 0, mult = 0;
    result = 1;
    mult = base;
    while (exp != 0)
    {
        if (exp % 2 != 0)
            result = result * mult % MOD;
        mult = mult * mult % MOD;
        exp /= 2;
    }
    return result;
}

struct SqrtCounter
{
    vector<LL> c, ps;

    SqrtCounter(LL x) : c(isqrt(x) + 1), ps(isqrt(x) + 1) {}

    LL count(LL x)
    {
        if (x <= 3)
            return 1;
        return c[isqrt(x)] * pow_mod(2, x - sq(isqrt(x))) % MOD;
    }

    LL prefix_sum(LL x)
    {
        if (x == 2)
            return 1;
        if (x == 3)
            return 2;
        return (ps[isqrt(x)] +
                c[isqrt(x)] * (pow_mod(2, x - sq(isqrt(x)) + 1) - 2 + MOD) % MOD) %
               MOD;
    }
};

int main()
{
    LL x = 0, sqrt_x = 0;
    cin >> x;
    SqrtCounter counter(x);
    counter.c[2] = 1;
    counter.ps[2] = 3;
    for (LL y = 3; y <= isqrt(x); ++y)
    {
        counter.c[y] = (counter.prefix_sum(sq(y) - 1) - counter.prefix_sum(y) + MOD) % MOD;
        counter.ps[y] = (counter.prefix_sum(sq(y) - 1) + counter.c[y]) % MOD;
    }
    cout << counter.count(x) << '\n';
}