import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String line=null;
			line=br.readLine();
			final int MAX = 1000000000;
			int n=Integer.parseInt(line),M[]=new int[n+1];
			M[1]=1;
			M[2]=2;
			for(int i=3;i<=n;i++){
				M[i]=i%2==0?M[i-2]+M[i>>1]:M[i-1];
				M[i]=M[i]>MAX?M[i]%MAX:M[i];
			}
			System.out.println(M[n]);
	}
}

• 不是有很多人用Java过了么=.=RE有时候不是开不出数组的问题…… (539) FinalLaugh 2006-10-24 16:20:51