[ABC006B] トリボナッチ数列
题意翻译
读入一个数a
f[1]=0,f[2]=0,f[3]=1,
f[n]=f[n-1]+f[n-2]+f[n-3];(因为数据过大所以要 mod 10007)
输出f[a]
Translated by @LW_h_FP
题目描述
[problemUrl]: https://atcoder.jp/contests/abc006/tasks/abc006_2
トリボナッチ数列というものがあります。この数列は3つ前までの数字を足したものです。
厳密には、
1\. $ a_1\ =\ 0 $, $ a_2\ =\ 0 $, $ a_3\ =\ 1 $
2\. $ a_n\ =\ a_{n-1}\ +\ a_{n-2}\ +\ a_{n-3} $
と定義されています。参考までに、トリボナッチ数列表を掲載します。
\# $ a_1 $ $ a_2 $ $ a_3 $ $ a_4 $ $ a_5 $ $ a_6 $ $ a_7 $ $ a_8 $ $ ... $ $ a_n $ 値 0 0 1 1 2 4 7 13 $ ... $ $ a_{n-1}+a_{n-2}+a_{n-3} $ この数列の第 $ n $ 項、$ a_n $ を $ 10007 $ で割った余りを求めてください。
入力は以下の形式で標準入力から与えられる。 > $ n $
整数 $ n(1≦n≦10^6) $ が $ 1 $ 行で与えられる。 トリボナッチ数列の第 $ n $ 項、$ a_n $ を $ 10007 $ で割った余りを $ 1 $ 行で出力してください。
また、出力の末尾には改行を入れること。 ```
<pre class="prettyprint linenums">
7
```
```
<pre class="prettyprint linenums">
7
```
- $ 7 $ 番目のトリボナッチ数は $ 7 $ です。
```
<pre class="prettyprint linenums">
1
```
```
<pre class="prettyprint linenums">
0
```
- 最初のトリボナッチ数は $ 0 $ です。
```
<pre class="prettyprint linenums">
100000
```
```
<pre class="prettyprint linenums">
7927
```
- $ a_n $ を $ 10007 $ で割った余りを出力することに気をつけてください。