题解：P12285 [蓝桥杯 2024 国 Python A] 药剂
一UNowen一
·
·
题解
对最终答案进行拆解可以发现最终答案应当是若干个a_{i}乘积乘上某个系数之和。使用简单的动态规划可以得到所有k个a_{i}的乘积之和。
因为每个a_{i}本质相同，因此所有乘数数量相同的乘积在最终答案里的系数应当是相同的，
令dp_{i,j}表示初始有i+j个数，将其中i个数打上标记，最终答案中打上标记的数的乘积的系数。
考虑如下转移
$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);
```