别问为什么现在才来写题解。
题目需要求分解 成若干个不同的斐波那契数列中的数有多少种方案。
由于每个位置最多一次，因此我们可以考虑用一个 字符串来表示。
这个 字符串有两个性质。如果 （换句话说，有连续的 110），那么将其替换成 也是合法的（即，替换为 001）。同理，你也可以考虑拆解。
不妨考虑拆解的情况。你发现，一旦你把 001 拆成 110，那么，第二个 就再也不能继续往下拆了。因为继续拆会变成 11010，第二个 仍然动不了。
证明可以对于字符串的长度归纳证明。换句话说，每个 11 第二个 无论如何都不可能分解成更小的两个 。
我们继续考虑，这样一定会分解成 11010101010 这种情况。碰到了下一个 就没办法继续分裂了（除非下一个 也分裂，但是这样最多多出来一个空位） 。
因此，每一段的分裂是相对独立的。这启示我们从一个分解开始，一直这样分裂下去。我们希望这个分解可以不被任何分裂方法到达，并且所有分解方式都可以被这个分解到达。
换句话说，考虑这样一个问题。考察 字符串，第 位的权值是 ，并且不允许连续两个或以上 在一起（这样挑最后两个 就能合并成更大的 ）。我们希望所有 位的权值和是 。
这实际上是一个类似“ 进制分解”之类的东西。我们不难猜出来下面这个结论：
对于任意一种 ，此类分解方式存在且唯一。
“存在”说明我们无论如何都能找到这样一个解。”唯一“则说明任意一个合法分解都可以通过这个分解到达。证明方法是从合法分解中不断挑出来两个相邻的 合并，合并到最后不能合并了就遇到了一个合法的这个分解。由于此类分解唯一，因此我们只要找到了一个解，我们就能断言最后到达的就是这个解。反过来就是说这个解可以到达所有题目要求的分解。
我们下面来证明一下这个命题。由于我们发现了这个命题和 进制分解的相似之处，因此我们也采用类似的证明方法，考虑数学归纳法。
不妨先来证明存在性。首先对于数列中的数 ，存在性是显然的。
不妨来考虑 位 字符串可以表示哪些数。我们考虑 DP，有转移方程 。边界条件是 。我们发现这其实就是斐波那契的第 项（下标从 开始）。
因此，我们可以考虑 位字符串可以表示 之间的数字。考虑归纳法。 的情况可以自行验证。不妨假设前 位都已经成立了。考虑最高位是什么。
- 对于 这个范围，我们直接最高位置 ，从 的情况继承过来。
- 对于 。我们最高位置 之后，接上 的一个解。这部分字符串的范围是 ，但我们又加上了 ，那么此时的范围就是 ，也就是 。
下面称这种分解为“标准分解”。
此外，我们刚刚证明了满足条件的不同的字符串个数恰好就是 个。因此这些分解都是唯一的。
唯一性也可以继续数学归纳，不过有点繁琐。但是我做这个题目的时候确实是这样推出来的，不写出来感觉自己亏了。
不妨假设 的部分已经证明完毕了。如果包含 则一定更大，因此长度增加一定不会影响前面的结论。考虑 这一部分。假设这个数是 ，第二种分解存在，那么第二种分解一定不包含 ，因为包含 剩下的数在 之间，根据归纳假设是唯一的，就是我们的标准分解。
那么，考察最高位是 。不妨考虑 这种情况。那么此时根据归纳假设， 的分解包含 ，那它要么不合法，要么就是标准分解。
考察 的情况。不妨考虑 ，那么 。
有归纳假设 的分解是唯一的。那么考虑 的分解是什么样子的。
不如考虑 的分解是什么样子的。手玩一下你会发现一定是 0000...101010101 或者 0000...10010101 这种形式。前面这段可以恰好放下 之间的所有数。
由于 ，那么 肯定小于 ，因此 影响的就是前面一段 0 的位置，对后面的 10 交错的部分不会影响。而在 10 交错的部分，给 置 会导致连锁进位一直进位到 。因此不存在除了标准分解之外的唯一分解。
另外，显然非标准分解额外置一个 也是非标准分解。因此我们就证明完毕了。
唯一分解可以通过贪心求出来，方法就是从高到低能减少就减少。
后面的工作就简单了。当然你可以每段组合数一堆求出来，但是分讨有点困难（考虑下一个分解的上一段会多一个空位）。
因此我们考虑 DP 求解。从高到低确定， 表示前 位，对后来的分解产生的 的影响是 。（ 表示 00 没有影响， 表示钦定后两位是 01 即第一位随便第二位一定是 ， 钦定后两位是 10，表示第一位一定是 第二位随意，3 表示后面两位都必须是 ，实际 1 不可能出现）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include <algorithm>
#include <array>
#include <iostream>
#include <vector>
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
namespace solve {
const uint mod = 1e9 + 7;
using mll = ull;
std::vector<ull> fib;
void prework() {
fib.push_back(1);
fib.push_back(2);
while (fib.back() <= 1e18) {
fib.push_back(fib.back() + fib[fib.size() - 2]);
}
return;
}
void solve() {
ull n;
std::cin >> n;
auto rfib = fib;
std::reverse(rfib.begin(), rfib.end());
std::vector<bool> std_fact(rfib.size());
for (size_t i = 0; i < rfib.size(); i++) {
if (n >= rfib[i]) {
n -= rfib[i];
std_fact[i] = true;
}
}
std::vector<std::array<mll, 4>> dp(rfib.size());
dp[0][0] = 1;
if (std_fact[0]) {
dp[0][3] = 1;
}
for (size_t i = 1; i < rfib.size(); i++) {
if (std_fact[i]) {
for (size_t j = 0; j < 4; j++) {
if (j == 3) {
continue;
}
if (j != 2) {
dp[i][3] += dp[i - 1][j];
}
if (!(j & 1)) {
dp[i][j >> 1] += dp[i - 1][j];
}
}
}
else {
for (size_t j = 0; j < 4; j++) {
dp[i][j >> 1] += dp[i - 1][j];
if (j == 1) {
dp[i][3] += dp[i - 1][j];
}
}
}
}
std::cout << dp.back()[0] << "\n";
}
}
int main() {
uint t;
std::cin >> t;
solve::prework();
while (t--) {
solve::solve();
}
std::cout << std::flush;
return 0;
}
>
|