問題一覧 > 通常問題

No.1269 I hate Fibonacci Number

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 42
作問者 : 👑 stoqstoq / テスター : noiminoimi
8 ProblemId : 5362 / 出題時の順位表
問題文最終更新日: 2020-10-17 12:33:53

問題文

フィボナッチ数列 $\{F_i\}$ は、 $F_0 = F_1 = 1, \ F_{i+2} = F_{i+1} + F_i \ (i \geq 0)$ で定義される数列です。 フィボナッチ数列に含まれる数をフィボナッチ数と言います。

次を全て満たす正の整数 $M$ の個数を $10^9+7$ で割った余りを求めてください。ただし桁数等は全て10進法で考えます。

  • $M$ の桁数は $N$ 以下である。
  • $M$ を文字列として見たときの連続する部分文字列で、数として $L$ 以上 $R$ 以下の フィボナッチ数となるものが存在しない。

例えば $M=1305$ は連続部分文字列としてフィボナッチ数 $1,3,5,05,13$ を含みます。($05$ は $5$ と等価です)

入力

$N\ L\ R$

  • 入力は全て整数
  • $1 \leq N \leq 5000$
  • $1 \leq L \leq R \leq 10^{18}$

出力

条件を満たす $M$ の個数を $10^9+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
1 1 9
出力
4

1以上9以下のフィボナッチ数は1, 2, 3, 5, 8です。これらを含まない1桁以下の正の整数は4, 6, 7, 9の4個です。

サンプル2
入力
2 2 2
出力
80

フィボナッチ数2が含まれない2桁以下の正の整数は80個です。

サンプル3
入力
100 123 456789101112
出力
629926418

$10^9+7$ で割った余りを求めてください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。