这道题一旦想开，其实思想十分简单的。
首先考虑n为奇数的情况，不难知f(n)=f(n-1)。（只需要把n的所有拆分式-1即可……）
然后考虑n为偶数的情况，将拆分式划分为两种情况：一种是式子中带1的，把1从式子中去掉就可以得到f(n-1)；一种是式子中不带1的，那么就把式子中的全部项除以2得到f(n/2)，则f(n)=f(n-1)+f(n/2)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 |
#include <stdio.h>#include<stdlib.h>#define DIV 1000000000int num[1000001]={0};int main(){ int
n,sum,i; num[1]=1; for(i=2;i<=1000000;i++) { if(i%2==1) { num[i]=num[i-1]; } else { num[i]=num[i-1]+num[i/2]; } num[i]%=DIV; } while(scanf("%d",&n)!=EOF) { printf("%d\n",num[n]); } return
0;} |
原文：http://www.cnblogs.com/wickedpriest/p/3581343.html