0 Judge
Code: 0
給定一長度為$N$的數列$A$=[$a_0$, $a_1$, ..., $a_{N-1}$],若一個數列$B$滿足以下兩個條件,則稱$B$是$A$的完美子序列:
$1.$ $B$是$A$的子序列,子序列的定義請參照提示
$2.$ 在$B$的尾端加入任意數字都將使$B$不再是$A$的子序列
若兩個完美子序列$X$、$Y$長度不同,或任一位置的數字不同(存在$i$使得$X_i \neq Y_i$,$0 \leq i < \left|X\right|)$),則稱$X$、$Y$為相異的完美子序列。
請計算$A$所有相異的完美子序列的總和。
子序列的和定義為子序列中所有數字加總,「所有相異完美子序列的總和」定義為所有相異完美子序列的和的加總。
例如,若輸入數列$A$為[1, 5, 1, 1, 5],則:
答案有可能很大,請輸出答案除以$10^9+7$的餘數。
小測資保證答案 $< 10^9+7$ ,正常計算即可,輸出也不必考慮取餘數的問題。
除了小測資外,輸入可能有多筆測資。 每一筆測資都在輸入檔案中佔用三行:
對於每一筆測資,輸出一行為所有相異完美子序列的總和。
在題目限制下,保證至少存在一種完美子序列。
請注意範例輸入最後一行後面是有換行符號的。
5
1 5 1 1 5
1
19
3
1 1 1
3
1 2 3
11
1 9 4 9 2 3 0 2 1 11 11
請注意範例輸出最後一行後面是有換行符號的。
84
19
3
18
15889
a. 子序列的定義為:在數列中任意刪除0個或多個數字,剩下的數字按照順序形成的數列,例如[1, 5]是[1, 6, 5]的子序列,但[5, 1]不是。空數列也算一個子序列,更詳細的說明請參照維基百科。
b. [1, 5, 1, 1, 5]的所有相異完美子序列條列如下:
[1, 1, 1, 5]
[1, 1, 5]
[1, 5, 1, 1, 5]
[1, 5, 1, 5]
[1, 5, 5]
[5, 1, 1, 5]
[5, 1, 5]
[5, 5]
總和為84。