← 返回题目列表

AtCoder · s8pc_4_e

E. 巨大的 Atcoder 铁路

中文机器翻译题面 查看原题
最高分数: 1000 积分

问题陈述

Atcoder王国有一家铁路公司,“Atcoder Railroad”。
有 N + 1 站编号 0, 1, 2, ..., N 沿着铁路。
目前运营两种列车:普通列车和特快列车。
普通列车每站都会停靠,距离车站仅需一分钟 i to i + 1,反之亦然。
特快列车只停站 S_0, S_1, S_2, ..., S_{K-1} (0 = S_0 < S_1 < S_2 < ... < S_{K-1} = N)。距车站 1 分钟 S_i to S_{i + 1},反之亦然。
但Atcoder Railroad公司的总裁Semiexp表示,这不是很方便,因此他打算再运营一种列车“半快车”。
半快车停靠的车站(这是 T_0, T_1, T_2, ..., T_{L-1}, 0 = T_0 < T_1 < T_2 < ... < T_{L-1} = N)必须遵循以下条件:
从车站 T_i to T_{i+1} 需要 1 分钟,反之亦然。
  • Atcoder王国的中心是车站 0,并且你必须能够去车站 i 最多 X 分钟。
  • 如果快车停站,半快车应停站。
打印半快车停靠站点集合的路数(顺序 T).
由于答案可能很大,因此打印数字模数 10^9 + 7.