菜单

ACM暑期培训-51Nod-1383

8月 1, 2018 - 算法
ACM暑期培训-51Nod-1383

前言

今天开始暑期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+4

Input
输入一个数N(1 <= N <= 10^6)
Output
输出划分方法的数量Mod 1000000007
Sample Input
7 Sample Output
6

这道题的核心思想在于一个递推的关系,对于奇数而言,其分解的结果无论怎么组合,都至少会有一个1单独出现,剩下的部分其实就是它之前的那个偶数的拆分情况,于是这个奇数的拆分方式就和它前面的偶数的拆分方式相同。
对于偶数而言,它的拆分方式可以分成有1和无1两种情况,有1的情况下与奇数类似,跟其前面的奇数分解方式相同,对于没有1的情况,把每个因子都除2,得到的是这个偶数一半的分解情况。
归纳成递推公式有

这也就是这个题的核心思想,第一次尝试的时候直接写成了递归形式,结果发现超时,于是改成dp的写法,代码如下:

后记

从dp的角度来说这肯定不算难题,不过对于我这样的老年人已经足够难写了,高中的时候就一直不很理解dp的奥义,希望接下来的几天能有点长进吧。

标签:, ,

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注