問題一覧 > 通常問題

No.1331 Moving Penguin

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 88
作問者 : penguinmanpenguinman / テスター : chineristACchineristAC
7 ProblemId : 5203 / 出題時の順位表
問題文最終更新日: 2021-01-17 18:21:42

問題文

$N$ 個のマス目が左右一列にあり、左から順にマス $1,\ 2,...N$ と呼ぶことにします。また、マス $i$ には整数 $A_i$ が書かれています。

Penguinman は今マス $1$ にいて、マス $N$ に移動しようとしています。

Penguinman はマス $i$ にいるとき、以下の条件のいずれかまたは両方を満たすマス $j\ (i<j≤N)$ に移動することができます。

  • $i≡j\ \bmod\ A_i$ である。
  • $i+1=j$ である。

Penguinman がマス $N$ に移動する方法は何通りありますか?答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを出力してください。

移動する方法を数えるにあたっては、経由したマスの集合のみを区別するものとします。

注意

時間制限の厳しい問題になっております。

PyPy3 による想定解の AC は確認しておりますが($900$ms 程度)、同様のコードを Python3 で投げたところ TLE しました。

Python ユーザーの方には PyPy3 による提出を推奨します。

入力

$N$
$A_1\ A_2\ ...\ A_N$
  • $2≤N≤10^5$
  • $1≤A_i≤N$
  • 入力は全て整数

出力

最後に改行してください。$\bmod$ を取ることを忘れないでください。

サンプル

サンプル1
入力
3
2 1 1
出力
2

マス $1→$ マス $2→$ マス $3$ と移動する方法と
マス $1→$ マス $3$ と移動する方法の $2$ 通りがあります。

サンプル2
入力
5
5 5 5 5 5
出力
1

任意のマスにおいて、$1$ つ先のマス目に移動することしかできません。

サンプル3
入力
10
5 1 9 1 1 3 4 2 1 10
出力
57

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