题目描述
一个整数总可以拆分为 2 的幂的和, 例如: 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式. 再比如: 4 可以拆分成: 4 = 4,4 = 1 + 1 + 1 + 1,4 = 2 + 2,4=1+1+2. 用 f(n) 表示 n 的不同拆分的种数, 例如 f(7)=6. 要求编写程序, 读入 n(不超过 1000000), 输出 f(n)%1000000000.
输入描述:
每组输入包括一个整数: N(1<=N<=1000000).
输出描述:
对于每组数据, 输出 f(n)%1000000000.
示例 1
输入
7
输出
6
解题思路
搬运一下思路:
记 f(n) 为 n 的划分数, 我们有递推公式:
f(2m + 1) = f(2m),
f(2m) = f(2m - 1) + f(m),
初始条件: f(1) = 1.
证明:
证明的要点是考虑划分中是否有 1.
记:
A(n) = n 的所有划分组成的集合,
B(n) = n 的所有含有 1 的划分组成的集合,
C(n) = n 的所有不含 1 的划分组成的集合,
则有: A(n) = B(n)C(n).
又记:
f(n) = A(n) 中元素的个数,
g(n) = B(n) 中元素的个数,
h(n) = C(n) 中元素的个数,
易知: f(n) = g(n) + h(n).
以上记号的具体例子见文末.
我们先来证明: f(2m + 1) = f(2m),
首先, 2m + 1 的每个划分中至少有一个 1, 去掉这个 1, 就得到 2m 的一个划分, 故 f(2m + 1)f(2m).
其次, 2m 的每个划分加上个 1, 就构成了 2m + 1 的一个划分, 故 f(2m)f(2m + 1).
综上, f(2m + 1) = f(2m).
接着我们要证明: f(2m) = f(2m - 1) + f(m),
把 B(2m) 中的划分中的 1 去掉一个, 就得到 A(2m - 1) 中的一个划分, 故 g(2m)f(2m - 1).
把 A(2m - 1) 中的划分加上一个 1, 就得到 B(2m) 中的一个划分, 故 f(2m - 1)g(2m).
综上, g(2m) = f(2m - 1).
把 C(2m) 中的划分的元素都除以 2, 就得到 A(m) 中的一个划分, 故 h(2m)f(m).
把 A(m) 中的划分的元素都乘 2, 就得到 C(2m) 中的一个划分, 故 f(m)h(2m).
综上, h(2m) = f(m).
所以: f(2m) = g(2m) + h(2m) = f(2m - 1) + f(m).
这就证明了我们的递推公式.
代码
- #include <iostream>
- using namespace std;
- int dp[1000001];
- int main()
- {
- dp[1] = 1;
- dp[2] = 2;
- for(int i = 3;i <= 1000000;i++)
- {
- if(i % 2 == 0)
- {
- dp[i] = (dp[i / 2] + dp[i - 1]) % 1000000000;
- }
- else dp[i] = dp[i - 1] % 1000000000;
- }
- int n;
- cin>> n;
- cout << dp[n] << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2562706.html