前言
今天开始暑期ACM培训了，第一天内容就讲了群论，反演，FFT这些东西，基本上超出了我对数学的理解范围QAQ。于是趁着脑子里还有点东西记录一下今天的题目。
整数分解为2的幂次(传送门戳我)
题目描述:
任何正整数都能分解成2的幂，给定整数N，求N的此类划分方法的数量！由于方案数量较大，输出Mod 1000000007的结果。 比如N = 7时，共有6种划分方法。
7=1+1+1+1+1+1+1
=1+1+1+1+1+2
=1+1+1+2+2
=1+2+2+2
=1+1+1+4
=1+2+4Input
输入一个数N（1 <= N <= 10^6)
Output
输出划分方法的数量Mod 1000000007
Sample Input
7 Sample Output
6
这道题的核心思想在于一个递推的关系，对于奇数而言，其分解的结果无论怎么组合，都至少会有一个1单独出现，剩下的部分其实就是它之前的那个偶数的拆分情况，于是这个奇数的拆分方式就和它前面的偶数的拆分方式相同。
对于偶数而言，它的拆分方式可以分成有1和无1两种情况，有1的情况下与奇数类似，跟其前面的奇数分解方式相同，对于没有1的情况，把每个因子都除2，得到的是这个偶数一半的分解情况。
归纳成递推公式有
|
1 2 3 4 |
F(1) = 1; F(2k+1) = F(2k) F(2k) = F(2k-1)+F(k) |
这也就是这个题的核心思想，第一次尝试的时候直接写成了递归形式，结果发现超时，于是改成dp的写法，代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <stdio.h> int main(int argc, char const *argv[]) { int n; scanf("%d", &n); int a[n+1]; a[1] = 1; for(int i = 2; i <= n; i++){ if(i%2 == 1) a[i] = a[i-1]; else if(i % 2 == 0) a[i] = (a[i-1]+a[i/2])%1000000007; } printf("%d\n", a[n]); return 0; } |
后记
从dp的角度来说这肯定不算难题，不过对于我这样的老年人已经足够难写了，高中的时候就一直不很理解dp的奥义，希望接下来的几天能有点长进吧。