TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

85.4% (35/41)

Submission's AC Ratio

37.7% (57/151)

Tags

Description

相信大家都有聽過知名的遊戲 Tetris,這是一個在三十幾年的時間內出現過無數不同版本的遊戲。

而最近的 Tetris 版本都有「保留」功能,也就是有一個保留按鍵能稍微改變出現的方塊順序。

具體來說,我們把出現的方塊當成一個序列 $a$ ,其中 $a_i$ 代表第 $i$ 個方塊的種類(注意到我們玩的 Tetris 很特殊,這裡的方塊可以不只七種),而玩家會按照順序遇到這些方塊。玩家有一個保留格,每次在放下一個方塊前可以選擇要不要將遇到的方塊 $a_i$ 保留;若不保留,則將直接把 $a_i$ 放下(我們不考慮放下後的位置之類的資訊,只在乎放下的順序);若選擇保留,則:

  • 當前保留格是空的:將 $a_i$ 放入保留格,且放下 $a_{i+1}$。
  • 當前保留格裝有 $a_j$ :將 $a_j$ 放下,同時將 $a_i$ 放入保留格。

特別注意,如果 $i = n$ ,且保留格是空的,那玩家不能選擇保留(保留了也沒有意義)。遊戲結束時,必須將所有方塊放下,也就是說,最後留在保留格中的方塊會被強制放下。

定義兩種玩遊戲的放下順序為不同,代表存在至少一個位置 $x$ 使得兩個放下順序中放下的第 $x$ 個方塊種類不同。請求出在按照規則使用保留鍵時有多少種玩遊戲的方法。由於方法數可能很多,請輸出答案模 $10 ^ 9 + 7$。

Input Format

對於所有測資,都有 $n \leq 2 \times 10 ^ 5, 1 \leq a_i \leq n$

第一行有一個整數 $n$,代表 $a$ 的長度。第二行有 $n$ 個整數 $a_1, a_2, \dots, a_n$。

Output Format

輸出答案模 $10 ^ 9 + 7$

Sample Input 1

3
1 2 3

Sample Output 1

4

Sample Input 2

7
3 1 2 2 4 1 2

Sample Output 2

42

Hints

範例測資一解釋:四種可能的方法為:"1, 2, 3", "1, 3, 2", "2, 1, 3", "2, 3, 1"

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~11 $n \leq 15$ 13
3 12~16 $\forall 1 \leq i \leq n, a_i = i$ 10
4 2~11, 17~26 $n \leq 1000$ 20
5 27~31 每一種方塊至多出現$10$次 16
6 2~42 無其他限制 41

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 2 4 6
3 1000 65536 65536 2 4 6
4 1000 65536 65536 2 4 6
5 1000 65536 65536 2 4 6
6 1000 65536 65536 2 4 6
7 1000 65536 65536 2 4 6
8 1000 65536 65536 2 4 6
9 1000 65536 65536 2 4 6
10 1000 65536 65536 2 4 6
11 1000 65536 65536 2 4 6
12 1000 65536 65536 3 6
13 1000 65536 65536 3 6
14 1000 65536 65536 3 6
15 1000 65536 65536 3 6
16 1000 65536 65536 3 6
17 1000 65536 65536 4 6
18 1000 65536 65536 4 6
19 1000 65536 65536 4 6
20 1000 65536 65536 4 6
21 1000 65536 65536 4 6
22 1000 65536 65536 4 6
23 1000 65536 65536 4 6
24 1000 65536 65536 4 6
25 1000 65536 65536 4 6
26 1000 65536 65536 4 6
27 1000 65536 65536 5 6
28 1000 65536 65536 5 6
29 1000 65536 65536 5 6
30 1000 65536 65536 5 6
31 1000 65536 65536 5 6
32 1000 65536 65536 6
33 1000 65536 65536 6
34 1000 65536 65536 6
35 1000 65536 65536 6
36 1000 65536 65536 6
37 1000 65536 65536 6
38 1000 65536 65536 6
39 1000 65536 65536 6
40 1000 65536 65536 6
41 1000 65536 65536 6
42 1000 65536 65536 6