hdu 5396 Expression

考虑到此题麻烦了某hust大神&体现出了自己数学能力的欠缺 虽然最近一直比较忙 还是把这题的题解写下来吧

首先看完数据范围后 应该有不少人会反应到是$n^3$的DP 以$F[i][j]$表示从i到j这个区间所有情况之和

然后再枚举中间点$k$从$F[i][k]$到$F[k+1][j]$转移过来 但此题绝不是想到DP就可以了

——————————————————————————————————————————–

我们假设合并时 左区间所包含的情况为$a1.a2……ap$右区间所包含的情况为 $b1.b2……bq$

对于乘法运算 由于乘法分配率这个性质 直接把两边所有情况之和乘起来就行了

对于加减法运算 左边的区间每个元素出现的次数为q 右边区间每个元素出现的次数为p

进一步 我们可以发现 出现次数p、q其实也就等于（区间长度-1）！ （感叹号代表阶乘 不要看错= =）

看起来该做的事情已经做完了 然而如果就这样写完代码 会发现连样例都过不了

———————————————————————————————————————————

多想想之后 我们发现这样一个问题 虽然合并时 左右区间都是确定的 然而达到同一个左右区间的方案并不是唯一的

我们先考虑一个比较小的情况 假设左区间通过$c1.c2$这两个操作得到  右区间通过$d1.d2$这两个操作得到

那么我们只要保证同一区间内操作的有序性即可使得最后得到的两个区间分别相同

比如$c1.c2.d1.d2$或$c1.d1.c2.d2$或……

这样可能的情况就有$C_{4}^{2}$种 推广到其他情况便是

C（（左区间长度-1）+（右区间长度-1），（左区间长度-1）） （注意到区间长度-1即为合并过程中的操作数）

于是这题便愉快地解决了

#include <bits/stdc++.h>
using namespace std;
const int N=,MOD=1e9+;
long long f[N][N],fac[N],c[N][N];
char s[N];
int n;
void prepare()
{
    fac[]=;
    for(int i=;i<=;++i)
        fac[i]=fac[i-]*i%MOD;
    c[][]=;
    for(int i=;i<=;++i)
    {
        c[i][]=;
        for(int j=;j<=i;++j)
        c[i][j]=(c[i-][j-]+c[i-][j])%MOD;
    }
}
void work()
{
    for(int i=;i<=n;++i)
    {
        scanf("%lld",&f[i][i]);
        for(int j=i+;j<=n;++j)
            f[i][j]=;
    }
    scanf("%s",&s[]);
    for(int len=;len<=n;++len)
    for(int i=;i+len-<=n;++i)
    {
        int j=i+len-;
        for(int k=i;k<j;++k)
        {
            if(s[k]=='*')
                f[i][j]+=f[i][k]*f[k+][j]%MOD*c[j-i-][k-i];
            else if(s[k]=='+')
                f[i][j]+=(f[i][k]*fac[j-k-]+f[k+][j]*fac[k-i])%MOD*c[j-i-][k-i];
            else
                f[i][j]+=(f[i][k]*fac[j-k-]-f[k+][j]*fac[k-i])%MOD*c[j-i-][k-i];
            f[i][j]%=MOD;
        }
    }
    //for(int i=1;i<=n;++i)
    //    for(int j=i;j<=n;++j)
    //        printf("%d %d %lld\n",i,j,f[i][j]);
    printf("%lld\n",(f[][n]+MOD)%MOD);}
int main()
{
    prepare();
    while(~scanf("%d",&n))
    work();
    return ;
}