整数分解为2的幂

wjh15101051's space

卧薪尝胆，厚积薄发。

整数分解为2的幂

Date: Mon Aug 27 20:48:08 CST 2018

In Category: NoCategory

Description：

给定整数 $n$ ，求 $n$ 划分为二的幂的方案数。

$1\le n \le 10^6$

Solution：

如果有一，那么可以减掉一个一，如果没有，可以全部除以二。

于是 $f[i]=f[i-1]+f[i / 2]\times[i\%2=0]$

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int f[MAXN];

#define MOD 1000000007

int main()

{

	scanf("%d",&n);

	f[0] = 1;

	for(int i = 1;i <= n;++i)

	{

		f[i] = f[i - 1];

		if(i % 2 == 0)f[i] += f[i / 2];

		f[i] %= MOD;

	}

	cout << f[n] << endl;

	return 0;

}

In tag: DP-DP

wjh15101051