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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3fffffff;
const ll mod=1e9+7;
const int maxn=100+10;
ll d[maxn][maxn],c[maxn][maxn],A[maxn],a[maxn];
char s[maxn];
void init()
{
A[0]=1;
c[0][0]=1ll; //
rep(i,1,maxn) A[i]=A[i-1]*i%mod;
c[1][0]=c[1][1]=1ll;
rep(i,2,maxn)
{
c[i][0]=c[i][i]=1ll;
rep(j,1,i) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
int main()
{
int n;
init();
while(~scanf("%d",&n))
{
memset(d,0,sizeof(d));
rep(i,1,n+1) scanf("%lld",&a[i]),d[i][i]=a[i];
scanf("%s",s+1);
for(int i=n-1;i>=1;i--)
{
for(int j=i+1;j<=n;j++)
{
for(int k=i;k<j;k++)
{
if(s[k]=='+')
d[i][j]=(d[i][j]+(d[i][k]*A[j-k-1]%mod+d[k+1][j]*A[k-i]%mod)%mod*c[j-i-1][k-i]%mod)%mod;
else if(s[k]=='-')
d[i][j]=(d[i][j]+(d[i][k]*A[j-k-1]-d[k+1][j]*A[k-i])%mod*c[j-i-1][k-i]%mod+mod)%mod;
else
d[i][j]=(d[i][j]+(d[i][k]*d[k+1][j]%mod)*c[j-i-1][k-i]%mod)%mod;
}
}
}
while(d[1][n] < 0)//可能小于0的。。不加会wa
d[1][n] += mod;
printf("%lld\n",d[1][n]%mod);
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=105;
const ll Mod=1000000007LL;
ll a[MAXN],f[MAXN];
char s[MAXN];
ll dp[MAXN][MAXN];
void build()
{
f[0]=1LL;
for(int i=1;i<=100;i++)
f[i]=i*f[i-1]%Mod;
}
ll fp(ll a,ll k)
{
ll res=1LL;
while(k>0)
{
if(k&1)res=res*a%Mod;
a=a*a%Mod;
k>>=1;
}
return res;
}
int main()
{
build();
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%I64d",&a[i]);
scanf("%s",s+1);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
dp[i][i]=a[i];
for(int len=1;len<n;len++)
{
for(int i=1;i+len<=n;i++)
{
int j=i+len;
for(int k=i;k<j;k++)
{
if(s[k]=='+')
dp[i][j]=(dp[i][j]+dp[i][k]+dp[k+1][j])%Mod;
else if(s[k]=='-')
dp[i][j]=(dp[i][j]+dp[i][k]-dp[k+1][j])%Mod;
else
dp[i][j]=(dp[i][j]+dp[i][k]*dp[k+1][j]%Mod)%Mod;
}
dp[i][j]=(dp[i][j]%Mod+Mod)%Mod;
dp[i][j]=dp[i][j]*fp(len,Mod-2)%Mod;
}
}
printf("%I64d\n",dp[1][n]*f[n-1]%Mod);
}
return 0;
}