#P6769. [2019备战noi]人生赢家djq

    ID: 6589 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>动态规划数论中国剩余定理贪心CF2400矩阵搜索数学

[2019备战noi]人生赢家djq

人生赢家 djq

题目描述

djq 将人生分为 nn 个阶段,用 11 到 nn 的一个排列 p1,p2,…,pnp_1,p_2,\ldots,p_n 表示各阶段的评分。

定义 p0=pn+1=0p_0=p_{n+1}=0。若

pi>pi−1且pi>pi+1,p_i>p_{i-1}\quad\text{且}\quad p_i>p_{i+1},

则称第 ii 个阶段为一个人生巅峰。因此,第一个和最后一个阶段也可能成为巅峰。

求恰好有 kk 个巅峰的排列数量,对 891003417891003417 取模。

输入格式

输入一行两个正整数 n,kn,k。

输出格式

输出一行一个整数,表示答案对 891003417891003417 取模的结果。

样例输入

3 1

样例输出

4

样例解释

满足条件的四个排列为 (1,2,3)(1,2,3)、(3,2,1)(3,2,1)、(1,3,2)(1,3,2) 和 (2,3,1)(2,3,1)。

数据范围

所有数据满足 1≤n≤10191\le n\le10^{19},1≤k≤min⁡(n,50)1\le k\le\min(n,50)。

数据比例(累计) nn 的上界
10%10\% 88
20%20\% 1212
40%40\% 10001000
60%60\% 10510^5
80%80\% 10910^9
100%100\% 101910^{19}

仅满足表中第 33、44、55 档范围的测试点中,每一档恰有一个测试点满足 k=1k=1,一个测试点满足 k=2k=2。