bzoj2656

题目链接:传送门

题目大意:已知 a0=0；a1=1； n为偶数 an=a(n/2)；n为基数 an=a(n/2)+a(n/2+1)；

题目思路:因为n过大，所以要用java高精度，还有最多20组数据，所以记忆化搜索一下

import java.io.*;

import java.math.*;

import java.util.*;

public class Main {

    public static HashMap<BigInteger, BigInteger> M=new HashMap<BigInteger,BigInteger>();

    public static Scanner in=new Scanner(new BufferedInputStream(System.in));

    public static void main(String args[]){

        M.put(BigInteger.valueOf(0),BigInteger.valueOf(0));

        M.put(BigInteger.valueOf(1),BigInteger.valueOf(1));

        solve();

        in.close();

    }

    public static void solve(){

        int group=in.nextInt();

        while(group--!=0){

            BigInteger num1=in.nextBigInteger();

            BigInteger ans=dfs(num1);

            System.out.println(ans);

        }

    }

    public static BigInteger dfs(BigInteger a){

        if(M.containsKey(a)) return M.get(a);

        BigInteger ta=a;

        if(a.mod(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(1))==0){

            a=a.divide(BigInteger.valueOf(2));

            BigInteger temp1=dfs(a);

            a=a.add(BigInteger.valueOf(1));

            BigInteger temp2=dfs(a);

            temp1=temp1.add(temp2);

            M.put(ta,temp1);

            return temp1;

        }

        else{

            a=a.divide(BigInteger.valueOf(2));

            BigInteger tt=dfs(a);

            M.put(ta,tt);

            return tt;

        }

    }

}