P8699 [蓝桥杯 2019 国 B] 排列数 题解

DreamLand_zcb · 2023-10-08 22:46:19 · 题解

题意

题目传送门

思路

设状态 dp[i][j] 其中 i 表示前 i 个数中，有 j 个折点的方案数。

考虑状态转移，显然 dp[i][j] 只能影响到 dp[i+1][j]、dp[i+1][j+1]、dp[i+1][j+2]，证明如下：

首先需要确定，在原序列中插入第 i + 1 个数，这个 i + 1 是所有数中最大的，所以只要在非头/尾部插入这个点，这个点一定就是新的折点。

1. 例： 情况一如图，当 $i + 1$ 插入波峰 $x$ 左右侧时，$x$ 不再是折点，折点变成了 $i + 1$，此时折点数不变。  情况二如图，当 $i + 1$ 插入序列头尾 $x$ 左右时，$x$ 依然不是折点，序列没有新增折点，此时折点数不变（如果头或尾的点是向下走的那么插入后新增了一个点，不属于该范围，此时只有在其中一边插入 $i + 1$ 才能满足不增加新折点）。 总结一下，当 $j$ 为奇数，总共 $\dfrac {j-1}2 \times 2 + 2 = j + 1$ 种可能。当 $j$ 为偶数，总共 $\dfrac {j}2 \times 2 + 1 = j + 1$ 中可能，所以转移方程： $$dp[i+1][j] = dp[i][j] \times (j + 1)$$
2. 只有一种情况，即当在序列头和尾向下走时在头和尾前后插入 $i + 1$ 只增加一个转折点，如图，$x$ 为新增的一个转折点。  所以转移方程： $$dp[i+1][j+1] = dp[i][j] \times 2$$
3. 显然在除了以上所有情况，其他地方插入 $i + 1$ 都会新增两个折点，转移方程： $$dp[i+1][j+2] = dp[i][j] \times (i + 1 - (j + 1) - 2)$$ $$ = dp[i][j] \times (i - j - 2)$$

初始值：dp[1][0] = 1、dp[i][0] = 2 (1 < i < n)。

答案：dp[n][k-1]。

代码

#include <bits/stdc++.h>
#define ll long long
#define setp setprecision
#define mem(a, m) memset(a, m, sizeof(a))
using namespace std;

const int MOD = 123456;
int n, k;
int dp[505][505];
int mod(int a)
{
    return a % MOD;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;
    dp[1][0] = 1;
    for(int i=2;i<n;i++)
    {
        dp[i][0] = 2;
        for(int j=0;j<=i;j++)
        {
            dp[i+1][j] += mod(dp[i][j] * (j + 1));
            dp[i+1][j+1] += mod(dp[i][j] * 2);
            dp[i+1][j+2] += mod(dp[i][j] * (i - j - 2));
        }
    }
    cout << dp[n][k-1] % MOD;
    return 0;
}