2016年发生了哪些重大事件？

本文共计1035个文字，预计阅读时间需要5分钟。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5698

题目描述：我们可以从一个格子跳到右下角的任意一个格子，那么反过来看，从右下角的格子跳到任意一个格子，其方法数显然就是其左上角所有格子的方法数之和。

题目链接：acm.hdu.edu.cn/showproblem.php?pid=5698

题意说我们可以从一个格子跳到右下角的任意一个格子中，那么反过来，跳到某一个格子的方法数显然就是其左上角的所有格子的方法数的和，那么问题又来了，我们怎么才能求出一个格子左上角的所有的格子的方法数和呢，树状数组？线段树？答案都不是，或许可以，不过我们并不需要那么做，观察仔细的同学应该发现每一个格子的方法数就等于其左边和上面的格子的方法数的和，这又是为什么呢？举个例子，比如我们要求的是(x,y)的方法数，那么其左边的格子的方法数和右边格子的方法数分别是以(1,1)和(x-2,y)的矩形和以(1,1)和(x,y-2)的矩形内的所有点的方法数和，不难发现这两个矩形重叠的部分就是以(1,1)到(x-2,y-2)的矩形，刚刚好相当于点(x-2,y-2)的方法数，所以这两个矩形的内的所有点的方法数和就等于(x,y)的方法数。

推出了每一个格子的方法数就等于其左边和上面的格子的方法数的和这个结论后，再仔细思考，我们能够直接通过这个结论得到答案吗，当然不行!!! 1e5的数据范围二维数组连开都开不出来，必须得用其他方法。

我们再来看这个序列，因为有每一个格子的方法数就等于其左边和上面的格子的方法数的和这个性质，所以我们很容易可以把这个和杨辉三角扯上关系，这个题就相当于一个横着的杨辉三角。