本文共 1680 字，大约阅读时间需要 5 分钟。

定义$f[i][j]$为区间$[i,j]$所有方案数的和

如何由小区间递推$f[i][j]?$

考虑枚举最后合并$[i,j]$的运算符$k$

若$k$位置是乘法

设$[i,k]$的不同方案数结果是$a_1,a_2...a_x$

设$[k+1,j]$的不同方案数的结果是$b_1,b_2...b_y$

相乘是$\sum _{i=1}^x\sum _{j=1}^y{a}_i\ast b_j=(\sum _{i=1}^x{a}_i)\ast (\sum _{j=1}^y{b}_j)$

也就是$f[i][k]\ast f[k+1][j]$

若$k$位置是加法呢??

相加是$\sum _{i=1}^x\sum _{j=1}^y(a_i+b_j)$

可以看到每个$a_i$被加了$y$次,每个$a_j$被加了$x$次

其实$x$就是$(k-i)!$就是运算符的阶乘,$y$就是$(j-k)!$

减法也是同理.

但是你以为就这么结束了吗???

注意虽然在区间$[i,k]$和$[k+1,j]$的运算顺序确定

但如果合并在一起还需要变化

也就是在$j-i$个操作符运算顺序选出$k-i$个按顺序放$[i,k]$的

另外的玩顺序放$[k+1,j]$的运算符,这样就完美了…

#include 
   
    using namespace std;#define int long longconst int maxn = 109;const int mod = 1e9+7;int n,f[maxn][maxn],w[maxn],c[maxn][maxn],fac[maxn];char a[maxn];void init(){
   	fac[0] = c[0][0] = 1;	for(int i=1;i<=100;i++)	fac[i]=fac[i-1]*i%mod;	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]+c[i-1][j-1] )%mod;	}}signed main(){
   	init();	while( cin >> n )	{
   		for(int i=1;i<=n;i++)	cin >> w[i],f[i][i] = w[i];		cin >> (a+1);		for(int l=2;l<=n;l++)		for(int i=1;i+l-1<=n;i++)		{
   			int j = i+l-1;			f[i][j] = 0;			for(int k=i;k
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109729580 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！