传送门：Count the Even Integers

ACM-ICPC 2017 Asia HongKong

题意

求出杨辉三角前 n n n层所有偶数的个数， n n n最大到 1 0 50 10^{50} 1050。

思路

打表找规律，设第 n n n层( n n n从 0 0 0开始)答案为 a n a_n an​，则可 OEIS 得到公式（OEIS A051679）
a 0 = a 1 = 0 a 2 n = 3 a n + n ( n − 1 ) / 2 a 2 n + 1 = 2 a n + a n + 1 + n ( n + 1 ) / 2 a_0=a_1=0 \\[1ex] a_{2n}=3a_n+n(n-1)/2 \\[1ex] a_{2n+1} = 2a_n+a_{n+1}+n(n+1)/2 a0​=a1​=0a2n​=3an​+n(n−1)/2a2n+1​=2an​+an+1​+n(n+1)/2

写Java大数递归的时候，注意用map记忆化一下，否则MLE。

AC代码（Java）

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main { 
	
	static BigInteger zero = BigInteger.ZERO;
	static BigInteger one = BigInteger.ONE;
	static BigInteger two = BigInteger.valueOf(2);
	static BigInteger three = BigInteger.valueOf(3);
	static Map<BigInteger,BigInteger>dp = new HashMap<>();

	public static void main(String[] args) { 
		Scanner cin = new Scanner(System.in);
		while(cin.hasNextBigInteger()) { 
			BigInteger n = cin.nextBigInteger();
			BigInteger ans = f(n.add(one));
			System.out.println(ans);
		}
	}
	
	static BigInteger f(BigInteger n) { 
		if(dp.get(n)!=null) return dp.get(n); 
		if(n==zero||n==one) { 
			return zero;
		}
		BigInteger res;
		if(n.mod(two)==zero) { 
			BigInteger h = n.divide(two); // n/2
			res = three.multiply(f(h)) // 3*f(h)
					.add(h.multiply(h.subtract(one)).divide(two)); // + h*(h-1)/2
		}
		else { 
			BigInteger h = n.subtract(one).divide(two); // (n-1)/2
			res = two.multiply(f(h)) // 2*f(h)
					.add(f(h.add(one))) // + f(h+1)
					.add(h.multiply(h.add(one)).divide(two)); // + h*(h+1)/2
		}
		dp.put(n, res); // dp[n]=res;
		return res;
	}

}