記dp_{l,r}dp?l,r??表示l,rl,r這段數能形成的答案總和。
枚舉最後一步操作kk，如果是乘法，答案為dp_{l,k}*dp_{k+1,r}dp?l,k??∗dp?k+1,r??，由於分配率這個會乘開來。如果是加法那麼是dp_{l,r}*(r-k-1)!+dp_{k+1,r}*(k-l)!dp?l,r??∗(r−k−1)!+dp?k+1,r??∗(k−l)!，即要乘上右邊k+1,rk+1,r這些數所有可行的方案數，減法同理。最後乘上{r-l-2 choose k-l}(?k−l?r−l−2??)，即把兩邊操作合起來的方案數。
答案為dp_{1,n}dp?1,n??。
Expression
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 447 Accepted Submission(s): 260
Problem Description Teacher Mai has
n numbers
a1,a2,?,anand
n−1 operators(+, - or *)
op1,op2,?,opn−1, which are arranged in the form
a1 op1 a2 op2 a3 ? an.
He wants to erase numbers one by one. In
i-th round, there are
n+1−i numbers remained. He can erase two adjacent numbers and the operator between them, and then put a new number (derived from this one operation) in this position. After
n−1 rounds, there is the only one number remained. The result of this sequence of operations is the last number remained.
He wants to know the sum of results of all different sequences of operations. Two sequences of operations are considered different if and only if in one round he chooses different numbers.
For example, a possible sequence of operations for
1+4∗6−8∗3 is
1+4∗6−8∗3→1+4∗(−2)∗3→1+(−8)∗3→(−7)∗3→−21.
Input There are multiple test cases.
For each test case, the first line contains one number
n(2≤n≤100).
The second line contains
n integers
a1,a2,?,an(0≤ai≤109).
The third line contains a string with length
n−1 consisting +,- and *, which represents the operator sequence.
Output For each test case print the answer modulo
109+7.
Sample Input
3
3 2 1
-+
5
1 4 6 8 3
+*-*
Sample Output
2
999999689
Hint Two numbers are considered different when they are in different positions.
Author xudyh
Source 2015 Multi-University Training Contest 9
/* ***********************************************
Author :CKboss
Created Time :2015年08月19日 星期三 21時58分12秒
File Name :HDOJ5396.cpp
************************************************ */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
