目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

有 \(n\) 个数字，每两个数字之间有两个运算符，求最后所有可能的值之和

State

\(2<=n<=100\)

\(0<=a[i]<=10^9\)

Input

3
3 2 1
-+
5
1 4 6 8 3
+*-*

Output

2
999999689

Solution

题目的意思将所有的运算符的优先级化为相同

\(dp[i][j]\) 表示区间 \([i,j]\) 上期望答案是多少

这使得 \(dp[i][j]\) 具有了可加性，\(dp[i][j]=\frac{\sum_{k=i}^{k<j}dp[i][k]@dp[k+1][j]}{j-i}\)，即每一个运算符都可以等可能的被选择

最后 \(dp[1][n]\) 即为所期望的答案，而根据运算符的选择顺序为 \(A_{n-1}^{n-1}\) 次

所以 \(dp[1][n]*(n-1)!\) 为所有可能的值之和

---

Code

const int mod = 1e9 + 7;
const int N = 100 + 5;
 
    int n, m, k, _;
    int a[N];
    char s[N];
    ll dp[N][N];

ll adp(ll &x)
{
    x %= mod;
    x += mod;
    x %= mod;
}

ll inv[N];
void get_inv(ll mod)
{
    inv[0] = inv[1] = 1;
    for(int i = 2; i < N; i ++){
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
}

signed main()
{
    // IOS;
    get_inv(mod);
    while(cin >> n){
        ll f = 1;
        ms(dp, 0);
        rep(i, 1, n){
            cin >> a[i];
            if(i != n) f = f * i % mod;
            dp[i][i] = a[i];
        }
        cin >> s + 1;
        for(int len = 2; len <= n; len ++){
            for(int i = 1; i <= n; i ++){
                int j = i + len - 1;
                if(j > n) break;
                for(int k = i; k < j; k ++){
                    if(s[k] == '+'){
                        dp[i][j] += dp[i][k] + dp[k + 1][j];
                    }
                    else if(s[k] == '-'){
                        dp[i][j] += dp[i][k] - dp[k + 1][j];
                    }
                    else dp[i][j] += dp[i][k] * dp[k + 1][j] % mod;
                }
                adp(dp[i][j]);
                dp[i][j] *= inv[len - 1];
                adp(dp[i][j]);
            }
        }
        pll(dp[1][n] * f % mod);
    }
    // PAUSE;
    return 0;
}