中石油训练赛 - Count the Even Integers(Java高精度运算+找规律)

题目大意：给出一个 n ，求出前 n 行的杨辉三角形中有多少个偶数

题目分析：先用暴力打个表，去oeis查一下，可以查出规律：

规律为一个递归，用记忆化搜索很容易实现：

n== 0 || n==1：a[ n ] = 0a[ 2 * n ] = 3 * a[ n ] + n * ( n - 1 ) / 2a[ 2 * n + 1 ] = 2 * a[ n ] + a[ n + 1 ] + n * ( n + 1 ) / 2

因为每次 n 都会除以 2 ，所以时间复杂度控制在了 log 级别，配合一个 map 写一下记忆化搜索就可以了

代码：  

import java.math.BigInteger; import java.util.Scanner; import java.util.HashMap; public class Main { public static Scanner cin = new Scanner(System.in); public static BigInteger _0=BigInteger.ZERO,_1=BigInteger.ONE,_2=BigInteger.valueOf(2),_3=BigInteger.valueOf(3); public static HashMap<BigInteger,BigInteger>mp=new HashMap<BigInteger,BigInteger>(); public static BigInteger dfs(BigInteger n) { if(mp.containsKey(n)) return mp.get(n); BigInteger ans=_0; if(n.compareTo(_0)==0||n.compareTo(_1)==0) ans=_0; else if(n.remainder(_2).compareTo(_0)==0)//偶数 { BigInteger n_div_2=n.divide(_2); ans=_3.multiply(dfs(n_div_2)).add(n_div_2.multiply(n_div_2.subtract(_1)).divide(_2)); } else//奇数 { BigInteger n_div_2=n.divide(_2); ans=_2.multiply(dfs(n_div_2)).add(dfs(n_div_2.add(_1))).add(n_div_2.multiply(n_div_2.add(_1)).divide(_2)); } mp.put(n,ans); return ans; } public static void main(String[] args) { while(cin.hasNextBigInteger()) { mp.clear(); BigInteger n=cin.nextBigInteger(); System.out.println(dfs(n.add(_1))); } } }