# 51Nod1383 -- power of integer to 2

51Nod1383 -- power of integer to 2

It's easy to think that for a certain number i, its combination can be regarded as each combination of i-1 plus a 1, but this 1 may merge with other 1 to generate a new combination;

When i is an odd number, it is found that one of them has not been merged all the time; for each combination of i-1, insert a 1. If a merger occurs, it will only occupy the position of 1 that needs to be merged and new combination will be generated, so no new combination will be generated at last;

But when i is an even number, because every combination of i-1 must have a 1 that has never been merged. At this time, inserting a 1 will merge and generate a new combination. At this time, find all the combinations of i-1 that have a 1 left. The combination of two ones must generate a new combination, and there will be no 1 in the new combination. How can these new combinations be recursive? After dividing these combinations by two, we find that these are the combinations of i/2.

Finally, the recurrence formula is established For ease of understanding, a certain number of combinations can be listed.

1=1

2=1+1=2

3=1+1+1=1+2

4=1+1+1+1=1+1+2=2+2=4

5=1+1+1+1+1=1+1+1+2=1+2+2=1+4

6=1+1+1+1+1+1=1+1+1+1+2=1+1+2+2=2+2+2=2+4=1+1+4

```#include <bits/stdc++.h>
#define For(i,x,y) for(int i=(x);i<=(y);++i)
#define Fov(i,x,y) for(int i=(x);i>=(y);--i)
#define Fo(i,x,y) for(int i=(x);i<(y);++i)
#define midf(a,b) ((a)+(b)>>1)
#define L(_) (_)<<1
#define R(_) ((_)<<1)|1
#define fi first
#define se second
#define ss(_) scanf("%s",_)
#define si(_) scanf("%d",&_)
#define sii(x,y) scanf("%d%d",&x,&y)
#define siii(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define sl(_) scanf("%I64d",&_)
#define mem(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
{
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar();}
while('0'<=ch&&ch<='9') { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int n_max=1e6+10;
int a[n_max];

int main()
{
//freopen("in.txt","r",stdin);
int n; si(n);
a=1;
For(i,1,n)
{
if(i&1) a[i]=a[i-1];
else a[i]=(a[i-1]+a[i>>1])%mod;
}
printf("%d\n",a[n]);
return 0;
}
```

Added by nashirak on Tue, 19 Nov 2019 21:54:58 +0200