[暑期集训][数学][递推] 51nod 1383

题意要求求出给定整数分解为2的幂之和的方法数量。(貌似这题还有两个加强版orz日后填坑

写出前几项后可以观察出来规律:当n为奇数的时候 f(n)=f(n-1),当n为偶数的时候f(n)=f(n/2)+f(n-2)。

这个规律的由来其实很简单,奇数的时候一定每一种分解都有至少一个1,说明这个1不是造成这些分法不同的原因,那么去掉他之后这些分法仍然是不同的,也就是数量没有减少,所以f(n)=f(n-1)。        而偶数的时候可以观察到分法可以分为两类,一类是有1的,这时候必定至少有两个1(因为n为偶数),换句话说这一类里面每种分法都有两个1,那么跟奇数那个同理这个也不是造成这些分法彼此不同的原因,所以去掉之后仍然是不同的也就是数量不会减少,这一部分相当于是f(n-2);   另一部分都是2的倍数,那么把他们全部除以2的话也仍然保持不同也就是数量没有变,也就是说这一部分相当于f(n/2)。

一开始没写记忆化果断T了几发。。。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=1000005;
const int MOD=1e9+7;

int a[maxn];

int f(int k)
{
    //cout<>1)%MOD+f(k-2)%MOD)%MOD;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    printf("%d\n",f(n));
    return 0;
}

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据