題目大意：給出一個(gè) n ，求出前 n 行的楊輝三角形中有多少個(gè)偶數(shù)

題目分析：先用暴力打個(gè)表，去oeis查一下，可以查出規(guī)律：

規(guī)律為一個(gè)遞歸，用記憶化搜索很容易實(shí)現(xiàn)：

n== 0 || n==1：a[ n ] = 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

因?yàn)槊看?n 都會(huì)除以 2 ，所以時(shí)間復(fù)雜度控制在了 log 級(jí)別，配合一個(gè) map 寫(xiě)一下記憶化搜索就可以了

代碼：
?

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)//偶數(shù){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//奇數(shù){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)));}} }

?

總結(jié)

以上是生活随笔為你收集整理的中石油训练赛 - Count the Even Integers(Java高精度运算+找规律)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。