自动搬运

查看原文

来自洛谷，原作者为

	Archmushroom 超鶸，但是超凶！

搬运于2025-08-24 21:33:59，当前版本为作者最后更新于2022-09-13 17:26:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题意

$n$ 个物体放进 $n$ 个格子。$i$ 号物体只能放在 $i - 1$ 号， $i$ 号或 $i + 1$ 号格，有多少种放法？

题目分析

老规矩 DP，$f_n$ 表示 $n$ 个物体放 $n$ 个格子的方案数。我们先看看 0 号物体放哪儿：

• 0 号物体放 0 号格：剩下 $n - 1$ 个物体放 $n - 1$ 个格子，方案数 $f_{n-1}$。
• 0 号物体放 1 号格：此时 1 号物体必须放 0 号格（否则 0 号格就没东西可放了）。剩下 $n - 2$ 个物体放 $n - 2$ 个格子，方案数 $f_{n-2}$。

综上转移函数是 $f_n = f_{n - 1} + f_{n - 2}$。没错，此题本质就是 Fibonacci，快速求 Fibonacci 数列第 n 项一般采用矩阵法：

$$\begin{bmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n $$

问题在于这里 $n \leq 10^{1000}$。对于如何处理这么大的整数，每篇题解都是八仙过海各显神通。不过本蒟蒻还是想到一种更简单易行的方法（明明很简单为什么大佬们都没写呢）。

核心内容

一句话概括：将快速幂从二进制扩展到十进制。原始的快速幂大家都理解了，在计算 $a^b$ 时：

• 如果 $b$ 的第零个二进制位为 $1$，则这一位对结果的贡献为 $a$;
• 如果 $b$ 的第一个二进制位为 $1$，则这一位对结果的贡献为 $a^2$;
• 如果 $b$ 的第二个二进制位为 $1$，则这一位对结果的贡献为 $a^4$;
• ......

那何不将其扩展到十进制的形式？

• 如果 $b$ 的个位为 $x$，则这一位对结果的贡献为 $a^x$;
• 如果 $b$ 的十位为 $x$，则这一位对结果的贡献为 $a^{10x}$;
• 如果 $b$ 的百位为 $x$，则这一位对结果的贡献为 $a^{100x}$;
• ......

这样做的好处是 $n$ 可以直接用字符串储存，而不需要使用高精度并将其转化为二进制了。

代码如下（只放核心的快速幂 $m^{pow}$ 部分，可以看到 $pow$ 是字符串而非整数）：

    matrix22 power(matrix22 m, std::string pow)
    {
        matrix22 result(1, 0, 0, 1);
        while(!pow.empty())
        {
            int pow_bit = pow.back() - '0';
            for(int i = 0; i < pow_bit; i++)
                result = result * m;
            m = m.pow10();
            pow.pop_back();
        }
        return result;
    }