传送门
有一个1*n的矩阵 固定第一个数为1 其他填正整数 且相邻数的差不能超过1 求方案数%1e9+7的结果
Input
一个数n 表示1*n的矩阵(n<=10^6)
Output
一个数 表示方案数%1e9+7的结果
Input示例
3
Output示例
5
解题思路:
这是一个默慈金数的题目,那么什么叫默慈金数呢。
默慈金数是在数学中,一个给定的数n的默慈金数是“在一个圆上的n个点间,画出彼此不相交的弦的全部方法的总数”。——摘自百度百科
默慈金数的实例表示:像例如在一个“网格”上,若限定“每步只能向右移动一格(可以向右上、右下横向向右),并禁止移动到 y=0 以下的地方”,则以这种走法用 n 步从 (0,0) 移动至 (n,0) 的可能形成的路径的总数为 n 的默慈金数。那么这个题目就是。本题是从(0, 1)出发,我们调整一下坐标轴即可,不影响后续的计算。
本题与默慈金数的模型的不同点是,我们要从 (0,0) 出发,而终点为 (n,x),x>=0。这时我们就需要逆向思维,已有模型不能帮助我们从正向推理出答案,但是可以帮助排除错误答案。因为默慈金数为(0,0)=>(x,0),如果在 x+1 处,我们向右下走,那么肯定不符合题目的限制,在 x+2...n 这一段无论怎么走,都是非法的。所以总的走法为 3n,然后排除所有的错误走法,就是最终的答案了。具体推出公式就是:ans[n] = 3?ans[n?1]?M[n?2] 其中M[n] 表示的是默慈金数。M[n]=(2?n+1)?M[n?1]+3?(n?1)?M[n?2]n+2
My Code
#include
#include
#include
#include
#include
#include