小码农

趣味编程-面向每个人的创意编程

蓝桥杯国赛:蓝跳跳

avatar 2022-11-17 15:11 839次浏览 0 条评论 题库

题目描述

小蓝制作了一个机器人,取名为蓝跳跳,因为这个机器人走路的时候基本靠跳跃。

蓝跳跳可以跳着走,也可以掉头。蓝跳跳每步跳的距离都必须是整数,每步可以跳不超过 k 的长度。由于蓝跳跳的平衡性设计得不太好,如果连续两次都是跳跃,而且两次跳跃的距离都至少是 p,则蓝跳跳会摔倒,这是小蓝不愿意看到的。

小蓝接到一个特别的任务,要在一个长为 L 舞台上展示蓝跳跳。小蓝要控制蓝跳跳从舞台的左边走到右边,然后掉头,然后从右边走到左边,然后掉头,然后再从左边走到右边,然后掉头,再从右边走到左边,然后掉头,如此往复。

为了让观者不至于太无趣,小蓝决定让蓝跳跳每次用不同的方式来走。小蓝将蓝跳跳每一步跳的距离记录下来,按顺序排成一列,显然这一列数每个都不超过 k 且和是 L。这样走一趟就会出来一列数。如果两列数的长度不同,或者两列数中存在一个位置数值不同,就认为是不同的方案。

请问蓝跳跳在不摔倒的前提下,有多少种不同的方案从舞台一边走到另一边。

输入格式

输入一行包含三个整数 k,p,L

输出格式

输出一个整数, 表示答案。答案可能很大, 请输出答案除以 20201114 的余数。

输入输出样例

输入 #1

3 2 5
输出 #1

9
输入 #2

5 3 10
输出 #2

397

说明/提示

【样例说明】

蓝跳跳有以下 9 种跳法:

  1. 1+1+1+1+1
  2. 1+1+1+2
  3. 1+1+2+1
  4. 1+2+1+1
  5. 2+1+1+1
  6. 2+1+2
  7. 1+1+3
  8. 1+3+1
  9. 3+1+1

【评测用例规模与约定】

对于 30% 的评测用例, 1≤p≤k≤50,1≤L≤1000

对于 60% 的评测用例, 1≤p≤k≤50,1≤L≤109

对于 80% 的评测用例, 1≤p≤k≤200,1≤L≤1018

对于所有评测用例, 1≤p≤k≤1000,1≤L≤1018

蓝桥杯 2020 年国赛 A 组 J 题。

发表评论