蓝桥杯 2019国B：排列问题的线性动态规划解法

[蓝桥杯 2019 国 B] 排列数

题目描述

在排列结构中，折点被定义为某个特定元素，该元素同时小于其左右相邻的两个元素，或者同时大于其左右相邻的两个元素。

若一个 1 ∼ n 的排列中存在 t 个折点，则该排列被称为 t + 1 单调排列。

例如，在排列 (1, 4, 2, 3) 中，4 和 2 均为折点，因此该排列属于 3 单调排列。

现给定数值 n 和 k，求解在所有由 1 ∼ n 构成的排列中，共有多少个属于 k 单调排列的情况？

输入格式

输入一行数据，其中包含两个整数 n 与 k。

输出格式

输出一个整数作为答案即可。若答案数值较大，只需计算满足条件的排列总数除以 123456 所得的余数进行输出。

样例分析与呈现

样例输入 #1

    4 2
    
    
      
    

样例输出结构解析

    12
    
    
      
    

提示

针对 20 \% 的测试案例，参数范围设定为 1 \leq k \leq n \leq 10；

针对 40 \% 的测试案例，参数范围设定为 1 \leq k \leq n \leq 20；