2229.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include "stdio.h"
#define MAX 1000001
#define U unsigned long

U kn[MAX];

int main(){
	long i,j,n,max;
	U sum;
	scanf("%d",&max);
	kn[1]=1;
	kn[2]=2;
	for (i=3;i<=max;i++)
		if (i%2) kn[i]=kn[i-1];
		else kn[i]=(kn[i-1]+kn[i/2])%1000000000;
	printf("%ld\n",kn[max]);
	return 0;
}