题目详情题解（0）讨论（0）提交记录（0）

AT_abc401_c.[ABC401C] K-bonacci

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定正整数 NN 和 KK。我们按照以下方式定义长度为 N+1N+1 的数列 A=(A0,A1,…,AN)A=(A_0,A_1,\ldots,A_N) 的每个元素值：

  • 当 0≤i<K0 \leq i < K 时，Ai=1A_i = 1
  • 当 K≤iK \leq i 时，Ai=Ai−K+Ai−K+1+…+Ai−1A_i = A_{i-K} + A_{i-K+1} + \ldots + A_{i-1}

请计算 ANA_N 对 10910^9 取模后的结果。

输入格式

输入通过标准输入给出，格式如下：

NN KK

输出格式

输出答案。

输入输出样例

  • 输入#1

    4 2

    输出#1

    5

  • 输入#2

    10 20

    输出#2

    1

  • 输入#3

    1000000 500000

    输出#3

    420890625

说明/提示

约束条件

  • 1≤N,K≤1061 \leq N, K \leq 10^6
  • 输入的所有数值均为整数

样例解释 1

A0=A1=1A_0 = A_1 = 1，而 A2=A0+A1=2A_2 = A_0 + A_1 = 2，A3=A1+A2=3A_3 = A_1 + A_2 = 3，A4=A2+A3=5A_4 = A_2 + A_3 = 5。

样例解释 3

请注意需要输出 ANA_N 对 10910^9 取模后的结果。

翻译由 DeepSeek V3 完成

输入解题思路，AI测评打分。不知道怎么写?

首页