组合数学-杨辉三角
题目描述
下面的图形是著名的杨辉三角形:
如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...
给定一个正整数 $N$,请你输出数列中第一次出现 $N$ 是在第几个数?
输入格式
输入一个整数 $N$。
输出格式
输出一个整数代表答案。
数据范围
对于 $20\\%$ 的评测用例,$1 ≤ N ≤ 10$;
对于所有评测用例,$1 ≤ N ≤ 10^9$。
输入样例:
6
输出样例:
13
算法
杨辉三角的一些特性:杨辉三角
要找到第一个出现的target,它一定出现在杨辉三角的左半个边。(显然)
1
1
1 2
1 3
1 4 6
1 5 10
考察这半个杨辉三角,以$1 1 1 1 …$为第0斜边,则第k斜边以$C_{2k}^{k}$开始,且斜边数字依次递增,斜边的第$i$($i>=0$)个值为$C_{2k+i}^{k}$。
首先确定target可能在哪个斜行,由于$C_{34}^{17}\gt10^9$,因此至多只需要枚举到第16斜行即可。
从第16斜行开始倒着枚举。因为越深的斜行的数值增长越快。
在一个斜行内,由于数值单调递增,可以用二分查找其位置。
若最终答案为:$C_{r}^{k}$,说明在第$r$横行($r\ge 0$)第$k$斜行,那么该元素是第$\frac{r(r+1)}{2}+k+1$个元素。
代码
package lanqiao.java_p_12;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class 杨辉三角 {
static BufferedWriter writter = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static long target = 0;
public static void main(String[] args) throws IOException {
target = Long.parseLong(reader.readLine());
for(int k=16; k>=0; k--) //k: 斜行index,此处先枚举大斜行
if(check(k, target))
break;
writter.close();
reader.close();
}
public static long C(long a, long b) // C_{a}^{b}
{
long res = 1;
for(long i=a, j=1; j<=b; i--, j++)
{
res = res*i /j;
if(res > target) return res; //不需要确切的组合数值,也防止爆long
}
return res;
}
//判断第k斜行是否包含target
//第k斜行: C_{P}^{k}, 其中P>=2*k
public static boolean check(long k, final long target) throws IOException
{
long l = 2*k, r = target; //枚举组合数"下标"
while(l < r)
{
long mid = l+r >> 1;
if(C(mid, k) >= target)
r = mid;
else l = mid+1;
}
if(C(r, k) != target || l > r) return false; //找不到target || target == 1
//找到了 C_{r}^{k}==target, 处于第r横行,第k斜行
writter.write(r*(r+1)/2 + k+1 +"\n");
return true;
}
}