题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5396
题意：
给出一个有n个数字，运算符只有"+","-","*"的表达式，每次合并相邻两项，求所有合并方式所得到的最终结果之和对1e9+7取模的值。
分析：
如果将这个过程随机化，即每次等概率地选取相邻两项合并，
记dp[i][j]为随机合并第i个到第j个数字这一段的表达式之后结果的期望，
根据期望的线性可加性，状态转移方程为
dp[i][j]=(sigma_(k=i~j-1)(dp[i][k]?dp[k+1][j]))/(j-i)，
其中"?"表示第k个数与第k+1个数之间的运算符，
那么dp[1][n]即为随机合并整个表达式之后结果的期望，
乘上方案数(n-1)!即为所求的总和，
由于是取模意义下的运算，转移方程中的除法要用逆元代替，
复杂度O(n^3)。
代码：
#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;
}