【多校第9场】【组合数学】【区间dp】【Expression】

本文主要是介绍【多校第9场】【组合数学】【区间dp】【Expression】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Expression

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 370 Accepted Submission(s): 208

Problem Description

Teacher Mai has

n numbers

a1,a2,⋯,an and

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
999999689Hint
 Two numbers are considered different when they are in different positions.

Author

xudyh

Source

2015 Multi-University Training Contest 9

Recommend

wange2014 | We have carefully selected several similar problems for you: 5405 5404 5403 5402 5401

#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#include <string>
#include <queue>
#include <bitset>
using namespace std;int n;
const int N = 210;
const int MOD = 1e9 + 7;
typedef long long ll;
int a[N];
char op[N];
ll dp[N][N];
ll comb[N][N];
ll fac[N];
void init()
{comb[0][0] = 1;for(int i=0;i<=101;i++){comb[0][i] = 0;comb[i][0] = 1;for(int j=1;j<=i;j++)comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;}fac[0] = 1;for(int i=1;i<=101;i++) fac[i] = fac[i-1] * i % MOD;}int main()
{init();while(scanf("%d",&n) != EOF){for(int i=0;i<n;i++){scanf("%d",&a[i]);}scanf("%s",op);for(int j=0;j<n;j++) {dp[j][j] = a[j];for(int i=j-1;i>=0;i--) {dp[i][j] = 0;for(int k=i;k<j;k++) {if(op[k] == '*') {dp[i][j] = (dp[i][j] + (dp[i][k] * dp[k+1][j]) % MOD * comb[j-i-1][k-i]) % MOD;}else if(op[k] == '+') {dp[i][j] = (dp[i][j] + (dp[i][k] * fac[j-k-1] + dp[k+1][j] * fac[k-i]) % MOD * comb[j-i-1][k-i]) % MOD;}else{dp[i][j] = (dp[i][j] + (dp[i][k] * fac[j-k-1] - dp[k+1][j] * fac[k-i]) % MOD * comb[j-i-1][k-i]) % MOD;}}}}if(dp[0][n-1] < 0) dp[0][n-1] += MOD;printf("%I64d\n",dp[0][n-1]);}return 0;
}

这篇关于【多校第9场】【组合数学】【区间dp】【Expression】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！