百度之星 初赛2 瞬间转移 [杨辉三角]

传送阵：http://acm.hdu.edu.cn/showproblem.php?pid=5698

瞬间移动

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 128 Accepted Submission(s): 61

Problem Description
有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第n行第m列的格子有几种方案，答案对1000000007取模。

Input
多组测试数据。

两个整数n,m(2≤n,m≤100000)

Output
一个整数表示答案

Sample Input
4 5

Sample Output
10

Source
2016”百度之星” - 初赛（Astar Round2B）

————————————————————————–

其实写了写就是一个杨辉三角，只不过行变换了一下

杨辉三角是一个由数字排列成的三角形数表,一般形式如下：
　　1 n=0
　　1 1 n=1
　　1 2 1 n=2
　　1 3 3 1 n=3
　　1 4 6 4 1 n=4
　　1 5 10 10 5 1 n=5
　　1 6 15 20 15 6 1 n=6
　　……
特征
　　与二项式定理的关系：杨辉三角的第n行就是二项式 展开式的系数列.
　　对称性：杨辉三角中的数字左、右对称,对称轴是杨辉三角形底边上的“高”.
　　结构特征：杨辉三角除斜边上1以外的各数,都等于它“肩上”的两数之和.
　　这些数排列的形状像等腰三角形,两腰上的数都是1.
　　从右往左斜着看,从左往右斜着看,和前面的看法一样,这个数列是左右对称的.
　　上面两个数之和就是下面的一行的数.
　　这行数是第几行,就是第二个数加一.

而在本题中 是这样的、
　　1 1 1 1 1 1 1
　　1 2 3 4 5 6
　　1 3 6 10 15
　　1 4 10 20
　　1 5 15
　　1 6
　　1

看了看其实就是行变了 列并没有变
把它改一下 行变成行加列-1 即可；

最后的最后直接贴上求组合数的模板AC…..

附本题AC 代码

方案1 187ms

————————————————————-

#include 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！