传送门:Count the Even Integers

ACM-ICPC 2017 Asia HongKong

题意

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

思路

打表找规律,设第$n$层($n$从$0$开始)答案为$a_n$,则可 ~~OEIS~~ 得到公式(OEIS A051679
$$
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
$$

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

}