#P14224. [2026队测系列]星港远征计划之cresc
[2026队测系列]星港远征计划之cresc
题目背景
在星港远征计划中,科研组正在研究一种分层增长谱。原始记录是一段长度为 的能级序列 ,其中每个值都在 到 之间。
系统只会保留相邻两项的和,从而生成一个长度为 的观测序列 。为了符合实验要求,这个观测序列必须是非递减的。
现在你需要计算,究竟有多少种不同的观测序列 可以由某个合法的原始序列 产生。
题目描述
对于一个长度为 的序列
我们按如下方式得到一个长度为 的序列
- 对每个 ,定义
请你求出满足以下全部条件的长度为 的序列 的个数,并对 取模:
- 是非递减序列;
- 存在一个长度为 的序列 ,其中每个元素都是 到 之间的整数(含端点),并且可以按上述方式得到该 。
输入格式
输入从标准输入给出,格式如下:
N M
输出格式
输出一行一个整数,表示答案。
样例 #1
输入
2 1
输出
5
说明
可能的 序列共有以下 种:
- ,得到
- ,得到
- ,得到
- ,得到
- ,得到
- ,得到
- ,得到
- ,得到
其中非递减的不同 共有 种:
样例 #2
输入
869121 10000000
输出
767557322
数据范围
- 输入中的所有值均为整数