前置 齐肯多夫定理
齐肯多夫定理的内容是：
任何正整数都可以被表示成若干不连续的斐波那契数之和（ 除外）
而对于一个正整数，我们可以按照二进制分解的策略：先贪心地找到一个最大的
满足 ，然后用 减去 ，以此类推直到减为 。
斐波那契数列一般定义为：，这里我们做一个整体左移，本文所述的斐波那契数列应是数列
，也就是
。
类比二进制，齐肯多夫分解是可以用一个 串表示出来的。例如：。因此它的齐肯多夫拆分就是：。
不难发现，按照贪心策略计算出的拆分是不会存在相邻的两个 的。因为一旦出现连续的 ，都可以遵循斐波那契数的定义把它变为一个更大的斐波那契数。
回归正题
假如我们现在已经得到了一个齐肯多夫拆分，如何计算题目要求的方案总数呢？
可以利用“标准齐肯多夫拆分中不存在相邻 ”的结论。对于原串的一个模式串
*100*（星号代表任意 串），我们可以拆成
*011*。如果在末尾的
后还有更多的 ，那其实也是可以再次拆分的。
注意到要求方案数，考虑动态规划。我们用 表示拆分中第 个 的出现位置，并令状态转移方程为 ，表示选择是否删除 位后的总方案数。
接下来考虑当前状态从何而来。如果选择不删当前这一位，答案只能从前一位
那里贡献而来，也即 。
如果选择删除这一位，对于接下来的操作，我们仍然可以选择删除或不删除。发现删到最后整个字符串一定是像
101010101 这样交错排列的。于是可以得到：
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
| #include <bits/stdc++.h>
#define N 90
using namespace std;
typedef long long ll;
vector<int> pos;
ll fib[N];
ll dp[N][2];
void init() {
fib[1] = fib[2] = 1;
for (int i = 3; i < N; i++) fib[i] = fib[i - 1] + fib[i - 2];
}
int solve(ll x) {
pos.clear();
for (int i = N - 1; i >= 1; i--) {
if (!x) break;
if (fib[i] <= x) {
x -= fib[i];
pos.push_back(i - 1);
}
}
reverse(pos.begin(), pos.end());
return pos.size();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
init();
while (t--) {
memset(dp, 0, sizeof dp);
ll x;
cin >> x;
int len = solve(x);
dp[0][0] = 1;
dp[0][1] = (pos[0] - 1) / 2;
for (int i = 1; i < len; i++) {
dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
dp[i][1] = dp[i - 1][0] * ((pos[i] - pos[i - 1] - 1) / 2) + dp[i - 1][1] * ((pos[i] - pos[i - 1]) / 2);
}
cout << dp[len - 1][1] + dp[len - 1][0] << endl;
}
return 0;
}
|
CF
通过记录
