杨辉三角前n行 偶数个数 与奇数个数

传送门

题意：

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

注意：杨辉三角有 第0层， 所以第n层，与第n行含义不同 第n行 为第n-1 层， 第0层 1 第1层 1 1 第2层 1 2 1 第3层 1 3 3 1 第4层 1 4 6 4 1 第5层 1 5 10 10 5 1 第6层 1 6 15 20 15 6 1 第7层 1 7 21 35 35 21 7 1 第8层 1 8 28 56 70 56 28 8 1 第9层 1 9 36 84 126 126 84 36 9 1

---

思路

打表找规律，发现 前n行 所有 偶数的个数公式 如下，

​ \quad (注意公式计算的结果 是 从0 层开始的 前n行的 偶数个数)

​ \quad (即 前4行 对应的 从0 层到 第 3层）

$$\begin{gathered} S_0=S_1=0 \\ {S}_{2n}=3S_n+\frac{n(n-1)}{2} \\ {S}_{2n+1}=2S_n+S_{n+1}+\frac{n(n+1)}{2} \end{gathered}$$

​ 直接 递归+记忆化(解决多组数据时递归爆内存 使用map 记录) +大数

java 大数的基础运用 https://blog.csdn.net/nefu__lian/article/details/108932598

---

AC代码（Java）

import java.util.HashMap; import java.util.Map; import java.util.Scanner; import java.math.BigInteger; public class Main{ static BigInteger one=BigInteger.ONE; static BigInteger zero=BigInteger.ZERO; static BigInteger two=BigInteger.valueOf(2); static BigInteger three=BigInteger.valueOf(3); static Map<BigInteger, BigInteger> mp=new HashMap<BigInteger, BigInteger>(); public static void main(String[] args) { Scanner in=new Scanner(System.in); BigInteger n,ans; while(in.hasNextBigInteger()) { n=in.nextBigInteger(); ans=f(n.add(one)); // n要 加1 的原因为 公式计算 前n层 , 而题目的 第N层 对应 公式的n+1 层 System.out.println(ans); } } static BigInteger f(BigInteger n) { BigInteger m,res; if(mp.get(n)!=null) return mp.get(n); if(n==one||n==zero) return zero; if(n.mod(two)==zero) { m=n.divide(two); res= three.multiply(f(m)) .add((m.multiply(m.subtract(one))).divide(two)); } else { m=n.subtract(one).divide(two); res=two.multiply(f(m)) .add(f(m.add(one))) .add(m.multiply(m.add(one)).divide(two)); } mp.put(n,res); return res; } }

---

 

思考 前n行 所有 奇数个数

 

[杨辉三角的性质]https://blog.csdn.net/nefu__lian/article/details/108932343

前n 行 共有多少个数字 （即前n-1层），符合等差 数列公式，公差为1

$S_n=n{a}_1+\frac{n(n-1)}{2}d=n+\frac{n^2-n}{2}=\frac{n(n+1)}{2}$ （n 为行 即n-1层）

奇数个数=总数-偶数个数

---

AC 代码（java）

注意这是前n行， 上面的代码时前 n 层

import java.util.HashMap; import java.util.Map; import java.util.Scanner; import java.math.BigInteger; public class Main{ static BigInteger one=BigInteger.ONE; static BigInteger zero=BigInteger.ZERO; static BigInteger two=BigInteger.valueOf(2); static BigInteger three=BigInteger.valueOf(3); static Map<BigInteger, BigInteger> mp=new HashMap<BigInteger, BigInteger>(); public static void main(String[] args) { Scanner in=new Scanner(System.in); BigInteger n,ans; while(in.hasNextBigInteger()) { n=in.nextBigInteger(); ans=f(n); System.out.println("前n行 偶数个数： "+ans); System.out.println("前n行 奇数个数： "+sum(n).subtract(ans)); } } static BigInteger f(BigInteger n) { // 前n行 偶数个数 BigInteger m,res; if(mp.get(n)!=null) return mp.get(n); if(n==one||n==zero) return zero; if(n.mod(two)==zero) { m=n.divide(two); res= three.multiply(f(m)) .add((m.multiply(m.subtract(one))).divide(two)); } else { m=n.subtract(one).divide(two); res=two.multiply(f(m)) .add(f(m.add(one))) .add(m.multiply(m.add(one)).divide(two)); } mp.put(n,res); return res; } static BigInteger sum(BigInteger n){ // 前n行 杨辉三角总数 return n.multiply(n.add(one)).divide(two); } }