[lg4133] [BJOI2012] 最多的方案

qwq

题意

求将一个正整数N分解成不同斐波那契数的和的形式的方案数。

思路

先证明一个貌似很显然的引理:

每个正整数一定有分解成不同斐波那契数的和的方案。

显然 对$ 1 , 2 $ 都成立。

假设对$ x \in [1,Fib_{i + 1})$成立,

那么对于$ x’ \in [Fib_{i + 1},Fib_{i + 2}) $ 有 $ x’ = x + Fib_{i + 1} $ 故可以归纳证明。

我们求一个最大分解方案,考虑对其分解。

$ v_i $表示这个分解方案中的第$ i $个数在斐波那契序列中的编号。

$ f_{ij} $表示考虑到第$ i $个数是否分裂的方案数。

对$ Fib_i $分解方案有$ \frac{i - 1}{2} $种。

考虑$ Fib_{i - 1} $是否分解。

如果不向下分割,方案有$ \frac{v_i - v_{i - 1} - 1}{2} $种。

如果向下分割,方案有$ \frac{v_i - v_{i - 1}}{2} $种。

然后转移。

Code

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
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
#include <vector>
typedef long long LL;
const LL fib[87] = {1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931};
inline LL getll()
{
LL r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
LL f[90][2];
std::vector<LL> v;
int main()
{
LL n = getll();
v.clear();
memset(f,0,sizeof(f));
for(int i = 86;~i;--i)
{
if(fib[i] <= n)
{
v.push_back(i + 1);
n -= fib[i];
}
}
std::reverse(v.begin(),v.end());
f[0][0] = 1;f[0][1] = (v.front() - 1) / 2;
for(int i = 1;i < (int)v.size();i++)
{
f[i][0] = f[i - 1][0] + f[i - 1][1];
f[i][1] = (v[i] - v[i - 1] - 1) / 2 * f[i - 1][0] + (v[i] - v[i - 1]) / 2 * f[i - 1][1];
}
printf("%lld\n",f[v.size() - 1][0] + f[v.size() - 1][1]);
return 0;
}