【题目描述】

nightmare是一个登山爱好者,今天他来到了黄山。

俗话说得好,不走回头路。所以在黄山,你只能往前走,或者往上走。并且很显然的是,当你走到山脊的时候,你不能够往上走,你只能往前走一步再往上走。

抽象一点而言就是,你可以把黄山视为一个N*N格点图,nightmare从(0,0)开始出发,要走到(N,N)。当他走到位置(x,y)的时候,它可以往(x+1,y)或(x,y+1)走。

并且当他走到(x,x)的时候,由于他已经处在了山脊上,所以它不能够往(x,x+1)方向上走。

当nightmare兴致勃勃准备开始爬山的时候,它的同伴告诉它,黄山由于年久失修,有一些位置出现了大坑,不能走。nightmare觉得更刺激了,但它想先知道它能有多少种方式走到黄山顶。

由于这个数字很大,所以你只需将答案对1000000007取模输出即可。

【输入格式】

第一行包括两个整数N,C,分别表示你可以把黄山视作一个N*N的格点图,并且黄山上有C个位置出现了大坑。

接下来的C行,每行包括两个整数X,Y,表示X,Y这个位置不能走。保证X≥Y,也就是说(X,Y)必然在山上。

保证这C个点互不相同。

【输出格式】

输出只有一个整数Ans,表示nightmare爬上山顶的路径数对1000000007取模的值。

【样例输入】

5 2

5 0

1 1

【样例输出】

27

【数据范围】

对30%的数据:N≤5000

另有20%的数据,C=0

另有20%的数据,C=1

对于100%的数据,N≤100000,C≤1000

保证对于(0,0)(N,N)不存在障碍点。

对于30%的数据直接DP即可。

对于C=0的情况,有个结论:从(0,0)走到(x,y)的方案数为C(x+y,x) 详情百度卡特兰数 (YYY神犇插板法证明Orz YYY神犇真是太神了!)

实际上,题意可以看出实际上就是不穿过这个格点图的对角线,画张图可以知道其实就是不穿过y=x+1这条直线,对于一个点(x,y)易证它关于y=x+1对称点为(y-1,x+1)

考虑补集的思想,从(0,0)到(x,y)的方案数就是总方案数-穿过y=x+1的方案数。而穿过y=x+1的方案数画一画图可以发现其实就是从(0,0)到(y-1,x+1)的方案数(相当于碰到y=x+1的一条路线关于y=x+1对称过去的路线,终点从(x,y)对称到了(y-1,x+1)) 所以C=1的情况迎刃而解,就是没限制的方案数-从(0,0)到(x,y)的方案数*(x,y)到(N,N)的方案数。

从C=1延伸到C>1 可以将所有障碍点和(N,N)视作关键点。

先将关键点按x坐标排序,设F[i]表示从(0,0)走到第i个关键点,途中不经过任何关键点的情况。同样考虑补集,可以设G[i]表示走到第i个关键点经过了第j个关键点的情况,那么我们枚举关键点j,令G[i]=∑j=(1 to i-1) F[j]*Ways[j][i],其中Ways[j][i]表示从j不穿过对角线走到i点的方案数,这个在上面已经讨论过怎么求了。然后最后F[i]=Ways[(0,0)–>Pi]-G[i]

对一个关键点O(C)解决,总复杂度O(C²)

做这道题数学能力一定要强,要思考呀!难点我觉得在那个C=0时候的结论。

另外,求组合数取模的时候用逆元来做。即A/B≡A*B^(P-2) (mod P)

下面是代码:

 

本文为原创文章,唯一地址链接:【登山】 转载请注明转自 stdKonjac

我来吐槽

*

*

取消

*

1位绅士参与评论

  1. Wiko10-26 22:23 回复

    ZZY你手打的痛苦吗?(´・_・`)