题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5396

题意：给你n个数和n-1个操作符（2<=n<=100），问你不断地每次给操作符的左右相邻的两个数加括号，直到最后只剩一个数为止，问你不同的方案的所有最终剩下一个数的和是多少。在一次取操作符时只要操作符的位置不相同就算一种方案。如果有n个操作符的话肯定有n!种方案。

解法：题解来自：点击打开链接设dp[i][j]为第i个数到第j个数的所有方案的和，那么假设我们已经枚举到区间i,j（i < j），对于加法和减法这两种情况是类似的，我们考虑第k个操作符（i<=k<j,假设k这个操作符是最后一次做的，两边的操作符都已经完成了），有

dp[i][j] += (dp[i][k] * A[j - (k + 1)] % mod + dp[k + 1][j] * A[k - i] % mod) % mod * C[j - i - 1][k - i] % mod

其中A数组储存阶乘值，C数组储存组合值。

为什么要乘以阶乘？对于左边的i到k来说，假设右边有n个符号，那么右边肯定有n！种方案，对于每个方案都要加上左边的总和，所以要乘以一个阶乘。同理右边。。。。为什么要乘以一个组合数？因为第k个操作符是最后取的，那么假设左边有n个操作符，右边有m个操作符，这么操作符取的顺序不同，最后的方案数也是不同的，所以我们把n+m个看作是取的顺序的位置，C[n + m][n]就相当与左边那些操作符放在哪些顺序的位置上。。。。

乘法的转移方程稍微有些不同，dp[i][j] += (dp[i][k] * dp[k + 1][j] % mod) * C[j - i - 1][k - i] % mod就行了


#include <bits/stdc++.h>
using namespace std;
const int maxn = 102;
typedef long long LL;
const int mod = 1e9+7;
LL dp[maxn][maxn]; //dp[i][j]第i个数到第j个数的方案总和
LL n, a[maxn];
char s[maxn];
LL fac[maxn], C[maxn][maxn];
int main()
{
    fac[0] = 1;
    for(int i=1; i<=100; i++) fac[i] = (fac[i-1]*i)%mod;
    C[0][0] = 1;
    for(int i=1; i<=100; i++){
        C[i][0] = 1;
        for(int j=1; j<=i; j++){
            C[i][j] = (C[i-1][j-1] + C[i-1][j])%mod;
        }
    }
    while(~scanf("%d", &n))
    {
        for(int i=1; i<=n; i++) scanf("%d", &a[i]), dp[i][i] = a[i];
        scanf("%s", s+1);
        for(int len = 2; len <= n; len++){
            for(int i=1; i+len-1<=n; i++){
                int j=i+len-1;
                dp[i][j]=0;
                for(int k=i; k<j; k++){
                    LL temp;
                    if(s[k] == '*')
                        temp = (dp[i][k]*dp[k+1][j])%mod;
                    if(s[k] == '+'){
                        temp = (dp[i][k]*fac[j-k-1]+dp[k+1][j]*fac[k-i])%mod;
                    }
                    if(s[k] == '-'){
                        temp = (dp[i][k]*fac[j-k-1]-dp[k+1][j]*fac[k-i])%mod;
                    }
                    dp[i][j] = (dp[i][j] + temp * C[j-i-1][k-i])%mod;
                }
            }
        }
        if(dp[1][n] < 0) dp[1][n] += mod;
        printf("%lld\n", dp[1][n]);
    }
    return 0;
}