题解：CF57C Array

· · 题解

题解：CF57C Array

题意

给定 n，求有多少不同的序列满足以下条件：

分析

显然单调不降的序列个数与单调不升的序列个数相等（只要左右翻转过来就能重合）

那么只要我们能求出单调不降的序列个数 cnt，答案 ans=2cnt-n，即把单调不降的和单调不升的个数加起来再减去 n 条被算 2 次的水平序列。

考虑如何求单调不降的序列个数，首先我想到了动态规划。设 dp_{i,j} 表示长度为 i，序列最后一项小于等于 j 的序列数量；边界为 dp_{1,1\sim n}=1；目标状态为 dp_{n,n}；状态转移方程为 dp_{i,j}=\sum_{k=1}^jdp_{i-1,k}，即把当前这一项接到序列末项小于等于它的序列后边。

但这样显然会超时，于是我们观察状态转移方程：

dp_{i,j}=\sum_{k=1}^jdp_{i-1,k}

变形：

dp_{i,j}=\sum_{k=1}^{j-1}dp_{i-1,k}+dp_{i-1,j}

代入：

dp_{i,j}=dp_{i,j-1}+dp_{i-1,j}

这个式子和杨辉三角的式子很像，为了更直观，下面给出 n=4 时的 dp 数组的值：

1  1  1  1
1  2  3  4
1  3  6  10
1  4  10 20

这里就很显然了，dp 数组正是杨辉三角旋转 45^\circ 后的样子，手玩一下下标发现 dp_{n,n} 对应杨辉三角中 2n-1 行 n-1 列，即组合数 C_{2n-1}^{n-1}，用组合数公式易得 dp_{n,n}=C_{2n-1}^{n-1}=\frac{(2n-1)!}{n!(n-1)!}

于是我们可以 O(n) 预处理阶乘，用费马小定理求逆元。

代码

// Array (AC)

#include <iostream>
using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;
const int N = 1e5 + 5;

ll n, jie[N << 1];

ll ksm(ll a, ll t)
{
    ll res = 1;
    while (t)
    {
        if (t & 1)
            res = res * a % mod;
        a = a * a % mod;
        t >>= 1;
    }
    return (res + mod) % mod;
}

ll c(int n, int m)
{
    return jie[n] * ksm(jie[m], mod - 2) % mod * ksm(jie[n - m], mod - 2) % mod;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;

    jie[0] = 1;
    for (ll i = 1; i <= n * 2; i ++)
        jie[i] = jie[i - 1] * i % mod;
    cout << (c(n * 2 - 1, n - 1) * 2 % mod + mod - n) % mod << endl;

    return 0;
}