人生赢家 djq
题目描述
djq 将人生分为 n 个阶段,用 1 到 n 的一个排列 p1,p2,…,pn 表示各阶段的评分。
定义 p0=pn+1=0。若
pi>pi−1且pi>pi+1,
则称第 i 个阶段为一个人生巅峰。因此,第一个和最后一个阶段也可能成为巅峰。
求恰好有 k 个巅峰的排列数量,对 891003417 取模。
输入格式
输入一行两个正整数 n,k。
输出格式
输出一行一个整数,表示答案对 891003417 取模的结果。
样例输入
3 1
样例输出
4
样例解释
满足条件的四个排列为 (1,2,3)、(3,2,1)、(1,3,2) 和 (2,3,1)。
数据范围
所有数据满足 1≤n≤1019,1≤k≤min(n,50)。
| 数据比例(累计) |
n 的上界 |
| 10% |
8 |
| 20% |
12 |
| 40% |
1000 |
| 60% |
105 |
| 80% |
109 |
| 100% |
1019 |
仅满足表中第 3、4、5 档范围的测试点中,每一档恰有一个测试点满足 k=1,一个测试点满足 k=2。