No.1847 Good Sequence
問題文最終更新日: 2022-02-18 18:41:19
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 332
(順位表)
の他の問題:
Problem Statement
You are given an integer $N$ and a sequence $K=K_1,K_2,\dots,K_M$ of $M$ elements consisting of integers between $1$ and $N$, inclusive.
A sequence $A=A_1,A_2,\dots,A_{L}$ of length $L$ satisfying the following conditions is called a good sequence.
- For every integer $i$ satisfying $1\leq i\leq L$, $A_i$ is an integer between $1$ and $N$, inclusive.
- There exists an $i$ such that there is a part where $K_i$ appears consecutively exactly $K_i$ times. That is, there exists a combination of integers $i,j$ satisfying all of the following 5 conditions simultaneously.
- $1\leq i\leq M$
- $0\leq j\leq L-K_{i}$
- $A_j\neq K_i$ or $j=0$
- $A_{j+K_i+1}\neq K_i$ or $j=L-K_{i}$
- $A_{j+1}=A_{j+2}= \dots =A_{j+K_i}=K_i$
Find the total number of good sequences, modulo $(10^{9}+7)$.
Constraints
- $1\leq L \leq 10^{18}$
- $1\leq N \leq 10$
- $1\leq M \leq N$
- $1\leq K_i \leq N$
- If $i\neq j$, then $K_i\neq K_j$
- All inputs are integers
Input
$L \; N\; M$ $K_1 \; K_2 \; \cdots \;K_M$
Output
Output the answer modulo $(10^{9}+7)$. Print a newline at the end.
Sample
Sample 1
Input
3 2 2 1 2
Output
4
The following 4 are the good sequences. $A=(1,2,1),(1,2,2),(2,1,2),(2,2,1)$
Sample 2
Input
1234567890 10 3 1 6 7
Output
393512451
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tatyam