ACM模版

描述

题解

首先，我们先来分析一下如何构造才合法。

先预处理出来每种大小的数的个数，并在这个过程进行判断是否连续（不大于 1 ），然后，我们可以从小到大进行插空法插数，那么如何插呢？假如，此时我们已经查到数 i ，那么合法的插孔分为两种，第一种是插在两个 i−1 之间，另一种就是当首尾有 i−1 时，我们可以在首尾两侧进行插空。那么我们需要考虑的也就是此时考虑到了第 i 种数、有多少个相邻的第 i 种数对儿、首尾有几个第 i 种数，自然最后这个状态只有三种，就是 0、1、2 ，所以我们设 dp[i][j][0/1/2] 表示此时考虑到了第 i 种数时，首尾第 i 种数的个数分别为 0、1、2 ，相邻的第 i 种数对儿个数加上首尾第 i 种数的个数的和为 j 时的方案数。初始化，我们应该设 dp[1][cnt[1]+1][2]=1 ，至于为什么，很容易理解，此时，第一种数的方案只有一种，首尾第一种数的个数为 2 ，连续的第一种数对儿为 cnt[1]−1 ，所以，你没有看错， cnt[1]+1 实际上就是此时插空时允许插空的数目。

综上所述，这个题核心就是插空法，组合数学的知识，另外还要使用一次插空法的地方是，要考虑将 cnt[i] 个数划分为 k 份时。

就这样，没有什么问题了，需要讲解的都说的十分清楚了，如果还有什么问题，可以评论区留言哦~~~

哦，对了，最后结果自然是不同插空数时三种情况的和的和喽！也就是说需要控制该 dp 的第二维的量，因为我们说明了，第二维实际上就是此时允许的插空数目。Over~~~

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 3e4 + 5;
const int MAXM = 111;
const int MOD = 1e9 + 7;

int n;
int A[MAXN];
int cnt[MAXN];
ll C[MAXM][MAXM];
ll dp[MAXN][MAXM][3];

template <class T>
inline bool scan_d(T &ret)
{
    char c;
    int sgn;
    if (c = getchar(), c == EOF)
    {
        return 0; //EOF
    }
    while (c != '-' && (c < '0' || c > '9'))
    {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}

void init()
{
    for (int i = 0; i < MAXM; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
        {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }
}

int main()
{
    init();

    scan_d(n);

    int tot = 0;
    for (int i = 1; i <= n; i++)
    {
        scan_d(A[i]);
        if (i == 1)
        {
            cnt[++tot] = 1;
            continue;
        }
        if (A[i] - A[i - 1] > 1)
        {
            puts("0");
            return 0;
        }
        if (A[i] - A[i - 1] == 1)
        {
            cnt[++tot] = 1;
        }
        else
        {
            cnt[tot]++;
        }
    }

    dp[1][cnt[1] + 1][2] = 1;
    for (int i = 1; i < tot; i++)
    {
        for (int j = 0; j <= cnt[i] + 1; j++)
        {
            int x = cnt[i + 1];
            for (int k = 1; k <= j; k++)
            {
                ll tmp = C[x - 1][k - 1];   // 将 x 个数划分为 k 份（插空法）
                if (x - k >= 0)
                {
                    dp[i + 1][x - k][0] += (dp[i][j][0] * C[j][k] % MOD
                                         + dp[i][j][1] * C[j - 1][k] % MOD
                                         + dp[i][j][2] * C[j - 2][k] % MOD) % MOD
                                         * tmp % MOD;
                    dp[i + 1][x - k][0] %= MOD;
                }
                if (x - k + 1 >= 0)
                {
                    dp[i + 1][x - k + 1][1] += (dp[i][j][1] * C[j - 1][k - 1] % MOD
                                             + dp[i][j][2] * C[j - 2][k - 1] * 2 % MOD) % MOD
                                             * tmp % MOD;
                    dp[i + 1][x - k + 1][1] %= MOD;
                }
                if (k - 2 >= 0 && x - k + 2 >= 0)
                {
                    dp[i + 1][x - k + 2][2] += dp[i][j][2] * C[j - 2][k - 2] % MOD * tmp % MOD;
                    dp[i + 1][x - k + 2][2] %= MOD;
                }
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i <= cnt[tot] + 1; i++)
    {
        ans = (ans + (dp[tot][i][0] + dp[tot][i][1] + dp[tot][i][2]) % MOD) % MOD;
    }
    cout << ans << endl;

    return 0;
}