前言
今天开始暑期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的奥义,希望接下来的几天能有点长进吧。