凌乱的地下室 题解
Archmushroom
·
·
题解
题意
## 题目分析
老规矩 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;
}
```