题解：P12285 [蓝桥杯 2024 国 Python A] 药剂

对最终答案进行拆解可以发现最终答案应当是若干个

a_{i}

乘积乘上某个系数之和。使用简单的动态规划可以得到所有

k

个

a_{i}

的乘积之和。

因为每个

a_{i}

本质相同，因此所有乘数数量相同的乘积在最终答案里的系数应当是相同的，

令

dp_{i,j}

表示初始有

i+j

个数，将其中

i

个数打上标记，最终答案中打上标记的数的乘积的系数。

考虑如下转移

dp_{i,j-1}\times i\times j\to dp_{i,j}

表示最后一次操作是合并一个有标记的数和无标记的数得到一个有标记的数，这次操作必定是加法操作，否则会破坏乘积的乘数只有有标记的数这一性质。

dp_{i,j-1}\times j\times (j-1)\to dp_{i,j}

表示最后一次操作是合并两个无标记的数，这次操作可以是加法操作也可以是乘法操作。

dp_{i-1,j}\times C_{i}^2\to dp_{i,j}

表示最后一次操作是合并两个有标记的数，这次操作必定是乘法操作。

枚举

i,j

进行转移

CPP


	dp[1][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=n;j++){
			if((i==1)&&(j==0))continue;
			if(j)add(1LL*i*j%mo*dp[i][j-1],dp[i][j]);
			if(j>1)add(1LL*j*(j-1)%mo*dp[i][j-1],dp[i][j]);
			if(i>1)add(1LL*i*(i-1)/2%mo*dp[i-1][j],dp[i][j]);
		}
	Dp[0]=1;
	for(int i=1;i<=n;i++){
		int x=read();
		for(int j=i;j;j--)add(1LL*Dp[j-1]*x,Dp[j]);
	}
	for(int i=1;i<=n;i++)add(1LL*Dp[i]*dp[i][n-i],ans);

题解：P12285 [蓝桥杯 2024 国 Python A] 药剂

文章操作

相关推荐

评论

题解：P12285 [蓝桥杯 2024 国 Python A] 药剂