ACM-ICPC 2017 Asia HongKong I題 Count the Even Integers【遞迴公式+記憶化】

傳送門：Count the Even Integers

ACM-ICPC 2017 Asia HongKong

題意

求出楊輝三角前$n$層所有偶數的個數，$n$最大到$10^{50}$。

思路

打表找規律，設第$n$層($n$從$0$開始)答案為$a_n$，則可 OEIS 得到公式（OEIS A051679）
$$\begin{gathered} a_0=a_1=0 \\ {a}_{2n}=3a_n+n(n-1)/2 \\ {a}_{2n+1}=2a_n+a_{n+1}+n(n+1)/2 \end{gathered}$$

寫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;
	}

}