ACM模版

描述

题解

这个题是一个典型的默慈金数的模型，在讨论区中，某大神已经详细的解释了这个数和这个题的转换关系。

首先，我们设 m[i]、f[i] 分别表示横坐标为 i 时的默慈金数和方案数。
那么，我们很容易得到的是默慈金数的表达式：

m[i]={i,m[i−1]∗(2∗i+1)+m[i−2]∗(3∗i−3)i+2,if i∈{1,2}if i>2
这里，我们更容易推出来 f[i] ，因为每个位置的方案数可以由前一个位置的方案数 ∗ 3 后减去不合法的，这里不合法的是多少呢？其实很好想，除去前一个位置方案终点在最下边的无法扩展出三条路，其他都是可以扩展出来的，那么我们只需要减去这无法扩展出来的一条路的路数即可，这个数是多少呢？恰好是 m[i−2] ，所以 f[i] 的递推方程很容易就出来了：
f[i]=f[i−1]∗3−m[i−2]
那么，有的人会疑问了，既然是前一个位置，为啥是 m[i−2] 而不是 m[i−1] 呢，这个评论区的某大神已经说得十分清楚了，因为我们这个默慈金数的模型和标准的不是完全一样的，我们需要对下标进行偏移后才刚好吻合。

这里注意用逆元，不然就挂了。

默慈金数真是一个有趣的东西，在《组合数学》一书中有讲，是卡特兰数的一个扩展好像。

OVER…

代码

#include <cstdio>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 10;

ll n;
ll f[MAXN];
ll m[MAXN];

ll inv(ll a, ll m)
{
    ll ret = 1;
    for (; m; m >>= 1, a = a * a % MOD)
    {
        if (m & 1)
        {
            ret = ret * a % MOD;
        }
    }

    return ret;
}

int main()
{
    scanf("%lld", &n);

    m[1] = f[1] = 1;
    m[2] = f[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        m[i] = (m[i - 1] * (2 * i + 1) % MOD + m[i - 2] * 3 * (i - 1) % MOD) % MOD
             * inv(i + 2, MOD - 2) % MOD;
        f[i] = ((f[i - 1] * 3 - m[i - 2]) % MOD + MOD) % MOD;
    }

    printf("%lld\n", f[n]);

    return 0;
}