传送门：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
);
res
= three
.multiply(f(h
))
.add(h
.multiply(h
.subtract(one
)).divide(two
));
}
else {
BigInteger h
= n
.subtract(one
).divide(two
);
res
= two
.multiply(f(h
))
.add(f(h
.add(one
)))
.add(h
.multiply(h
.add(one
)).divide(two
));
}
dp
.put(n
, res
);
return res
;
}
}
