No.695 square1001 and Permutation 4
レベル :
/ AI推定難易度 : 2000
/ 実行時間制限 : 1ケース 7.000秒 / メモリ制限
: 75 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 :
square1001
/ テスター :
e869120
タグ : / 解いたユーザー数 17
作問者 :
square1001
/ テスター :
e869120
問題文最終更新日: 2020-11-12 16:39:54
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 192
(順位表)
の他の問題:
Notice
- 2020. 11. 12 : Because a recent compiler update changed the JAVA version from the one in use when this problem was published (2018. 6. 8), the memory limit has been changed from 64 MB to 75 MB. Thank you for your understanding.
Problem Statement
Wait, where is "permutation"? - Just imagine it :)
There is a $1 \times n$ chessboard. Let square $i$ be the $i$-th square from the left.
A chess piece is on square $1$. When the chess piece is on square $i$, square1001 can move it to any one of squares $i+x_1, i+x_2, \cdots, i+x_m$.
Find the number of ways to move the piece such that it finally ends up on square $n$.
Since the answer can be very large, find it modulo $100 \ 000 \ 000 \ 000 \ 000 \ 007$.
Input
$n$ $m$ $x_1 \ x_2 \ \cdots \ x_m$
Output
Print $a_n$ modulo $100 \ 000 \ 000 \ 000 \ 000 \ 007$ on $1$ line.
Print a newline at the end.
Constraints
- $2 \leq n \leq 20 \ 000 \ 000$.
- $1 \leq m \leq 5$.
- $1 \leq x_i \leq n-1 \ (1 \leq i \leq m)$.
- $x_1, x_2, \dots, x_m$ are all distinct.
Sample
Sample 1
Input
5 2 1 2
Output
5
There are the following $5$ ways to move the piece.
- Square $1$ --> Square $2$ --> Square $3$ --> Square $4$ --> Square $5$
- Square $1$ --> Square $2$ --> Square $3$ --> Square $5$
- Square $1$ --> Square $2$ --> Square $4$ --> Square $5$
- Square $1$ --> Square $3$ --> Square $4$ --> Square $5$
- Square $1$ --> Square $3$ --> Square $5$
Sample 2
Input
1000000 5 3 14 159 2653 58979
Output
73305885902670558
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。