默慈金数

今天学习一下一个新的知识，“默慈金数”这是一个默慈金数的题目，那么什么叫默慈金数呢。

默慈金数是在数学中，一个给定的数n的默慈金数是“在一个圆上的n个点间，画出彼此不相交的弦

的全部方法的总数”。——摘自百度百科

具体以一个例题来说明一下：

有一个1*n的矩阵 固定第一个数为1 其他填正整数 且相邻数的差不能超过1 求方案数%1e9+7的结

果

Input

一个数n 表示1*n的矩阵（n<=10^6）

Output

一个数 表示方案数%1e9+7的结果

Input示例

3

Output示例

5

解题思路：

默慈金数的实例表示：像例如在一个“网格”上，若限定“每步只能向右移动一格(可以向右上、右

下横向向右)，并禁止移动到 $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$ 这一段无论怎么走，都是非法的。所以总的走法为 $3^n$，然后排除所有的错误走法，就

是最终的答案了。具体推出公式就是：$ans[n]$ $=$ $3*ans[n-1]-M[n-2]$ 其中$M[n]$

表示的是默慈金数。$M[n]=\frac{(2*n+1)*M[n-1] + 3*(n-1)*M[n-2]}{n+2}$

$My$ $Code$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const LL MOD = 1e9+7;
const int MAXN = 1e6+5;
LL ans[MAXN], M[MAXN];
void Exgcd(LL a, LL b, LL &x, LL &y)///求逆元
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    LL x1, y1;
    Exgcd(b, a%b, x1, y1);
    x = y1;
    y = x1-(a/b)*y1;
}
void get_Motzkin()///得到默慈金数
{
    LL x, y;
    M[1] = 1, M[2] = 2;
    for(int i=3; i<MAXN; i++)
    {
        Exgcd(i+2, MOD, x, y);
        x = (x%MOD+MOD)%MOD;
        M[i] = ( ((2*i+1)*M[i-1])%MOD + ((3*i-3)*M[i-2])%MOD ) * x;
        M[i] = (M[i]%MOD+MOD)%MOD;
    }
}
void Init()
{
    get_Motzkin();
    ans[1] = 1, ans[2] = 2;
    for(int i=3; i<MAXN; i++)
    {
        ans[i] = (3*ans[i-1]-M[i-2]);
        ans[i] = (ans[i]%MOD+MOD)%MOD;
    }
}
int main()
{
    Init();
    int n;
    while(~scanf("%d",&n))
    {
        printf("%I64d\n",ans[n]);
    }
    return 0;
}