【区间dp+组合数+数学期望】Expression

https://www.bnuoj.com/v3/contest_show.php?cid=9148#problem/I

【题意】

给定n个操作数和n-1个操作符，组成一个数学式子。每次可以选择两个相邻操作数及中间的操作符进行运算，如a-b变成一个数(a-b)，直到这个式子变成一个数。同一个初始式子可以进行不同的操作，最后的结果也可能不同。最后求不同操作得到结果的和（mod 1000 000 007）

对于两个操作，只要存在一步是不同的，这两个操作就被认为是不同的。

【思路】

总体思路是区间dp,对于dp[i][j]，枚举k(i<=k<j),考察dp[i][k]和dp[k+1][j]

具体做的时候可以分别考虑*,+,-三种运算，用组合数学；

还有一种非常非常巧妙的办法：数学期望！

组合数学：

比较明显的区间dp，令dp[l][r]为闭区间[l,r]的所有可能的结果和，考虑最后一个符号的位置k，k必须在l,r之间，则l≤k<r，dp[l][r]=Σ{dp[l][k]?dp[k+1][r]}*(r-l-1)!/[(k-l)!(r-k-1)!]，其中(r-l-1)!/[(k-l)!(r-k-1)!]表示从左区间和右区间选择符号的不同方法总数（把左右区间看成整体，那么符号的选择在整体间也有顺序，内部的顺序不用管，那是子问题需要考虑的)，相当于(k-l)个0和(r-k-1)个1放一起的不同排列方法总数。

对花括号里面的‘?‘分为三种情况：

(1)‘+‘ 假设左区间有x种可能的方法，右区间有y种可能的方法，由于分配律的存在，左边的所有结果和会重复计算y次，右边的所有结果和会重复计算x次，而左边共(k-l)个符号，右边共(r-k-1)个符号，所以合并后的答案dp[l][r]=dp[l][k]*(r-k-1)!+dp[k+1][r]*(k-l)!

(2)‘-‘ 与‘+‘类似

(3)‘*‘ 由分配律，合并后的答案dp[l][r]=dp[l][k]*dp[k+1][r]

数学期望：

如果将这个过程随机化，即每次等概率地选取相邻两项合并，

记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)。

【Accepted】

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<cmath>
 7 
 8 using namespace std;
 9 typedef long long ll;
10 const int maxn=1e2+5;
11 const ll mod=1e9+7;
12 ll a[maxn];
13 char op[maxn];
14 ll dp[maxn][maxn];
15 ll fpow(ll x,ll n)
16 {
17     ll res=1LL;
18     while(n)
19     {
20         if(n&1)
21         {
22             res=(res*x)%mod;
23         }
24         x=(x*x)%mod;
25         n>>=1;
26     }
27     return res;
28 }
29 ll fact[maxn];
30 ll nfact[maxn];
31 int n;
32 void init()
33 {
34     fact[0]=1LL;
35     for(int i=1;i<maxn;i++)
36     {
37         fact[i]=(fact[i-1]*(ll)i)%mod;
38     }
39     nfact[0]=1LL;
40     for(int i=1;i<maxn;i++)
41     {
42         nfact[i]=fpow(fact[i],mod-2);
43     }
44 }
45 int main()
46 {
47     init();
48     while(~scanf("%d",&n))
49     {
50         memset(dp,0,sizeof(dp));
51         for(int i=0;i<n;i++)
52         {
53             cin>>a[i];    
54         }
55         scanf("%s",op);
56         for(int i=0;i<n;i++)
57         {
58             dp[i][i]=a[i];
59         }
60         for(int l=1;l<n;l++)
61             for(int i=0;i+l<n;i++)
62             {
63                 int j=i+l;
64                 for(int k=i;k<j;k++)
65                 {
66                     ll add;
67                     if(op[k]=='+')
68                     {
69                         add=(dp[i][k]*fact[j-1-k]%mod+dp[k+1][j]*fact[k-i]%mod)%mod;
70                     }
71                     else if(op[k]=='-')
72                     {
73                         add=(dp[i][k]*fact[j-1-k]%mod-dp[k+1][j]*fact[k-i]%mod+mod)%mod;
74                     }
75                     else
76                     {
77                         add=(dp[i][k]*dp[k+1][j]%mod)%mod;
78                     }
79                     add=(add*fact[l-1]%mod*nfact[j-1-k]%mod*nfact[k-i]%mod)%mod;
80                     dp[i][j]=(dp[i][j]+add)%mod;    
81                 }
82             }
83         cout<<dp[0][n-1]<<endl;
84         
85     }
86     return 0;
87 }

区间dp+组合数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<cmath>
 7 
 8 using namespace std;
 9 typedef long long ll;
10 const ll md=1e9+7;
11 ll fpow(ll x,ll n)
12 {
13     ll res=1LL;
14     while(n)
15     {
16         if(n&1)
17         {
18             res=(res*x)%md;
19         }
20         x=(x*x)%md;
21         n>>=1;
22     }
23     return res;
24 }
25 const int maxn=1e2+3;
26 ll a[maxn];
27 char op[maxn];
28 ll dp[maxn][maxn];
29 ll fact[maxn];
30 void init()
31 {
32     fact[0]=1LL;
33     for(int i=1;i<maxn;i++)
34     {
35         fact[i]=(fact[i-1]*(ll)i)%md;
36     }
37 }
38 int n;
39 int main()
40 {
41     init();
42     while(~scanf("%d",&n))
43     {
44         memset(dp,0,sizeof(dp));
45         for(int i=0;i<n;i++)
46         {
47             cin>>a[i];
48         }
49         scanf("%s",op);
50         for(int i=0;i<n;i++)
51         {
52             dp[i][i]=a[i];
53         }
54         for(int l=1;l<n;l++)
55         {
56             for(int i=0;i+l<n;i++)
57             {
58                 int j=i+l;
59                 for(int k=i;k<j;k++)
60                 {
61                     ll add;
62                     if(op[k]=='+')
63                     {
64                         add=(dp[i][k]+dp[k+1][j])%md;
65                     }
66                     else if(op[k]=='-')
67                     {
68                         add=(dp[i][k]-dp[k+1][j]+md)%md;
69                     }
70                     else
71                     {
72                         add=(dp[i][k]*dp[k+1][j])%md;
73                     }
74                     dp[i][j]=(dp[i][j]+add)%md;
75                 }
76                 dp[i][j]=(dp[i][j]*fpow(l,md-2))%md;
77             }
78         }
79         ll ans=(dp[0][n-1]*fact[n-1])%md;
80         cout<<ans<<endl;
81     }
82     return 0;
83 }

区间dp+数学期望（随机化过程，期望的线性可加性）

【知识点】

1. 取模意义下的除法不能直接除，要用逆元代替。根据费马小定理，a^(p-1)=1(mod p),所以a^(p-2)=(1/a)(mod p),所以a的逆元就是a^p-2。通常p是一个很大的素数，如经常见到的1e9+7，所以要用快速幂。

快速幂模板

fastpow

 1 ll fpow(ll x,ll n)
 2 {
 3     ll res=1LL;
 4     while(n)
 5     {
 6         if(n&1)
 7         {
 8             res=(res*x)%mod;
 9         }
10         x=(x*x)%mod;
11         n>>=1;
12     }
13     return res;
14 }

2. 组合数C(i,j)有两种算法：
第一种：

fac(i+j)*nfac(i)*nfac(j) 
//其中nfac(i)=fastpow(fac(i),mod-2)

第二种：

C[0][0]=1;
    for (int i=0;i<201;i++)
    {
        C[i][0]=1;
        for (int j=1;j<=i;j++)
        {
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%md;
        }
    }

3. 在取模运算下，要注意减法，a-b通常要写成（a-b+md）%md

总之注意不要算出负数