自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:14:19，当前版本为作者最后更新于2025-04-23 16:39:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

本题的含义是，对于所有的方案最终药水的权值求和。

设全集 $U=\{1,2,3,\cdots,n\}$，定义其子集 $S \subseteq U$ 的权值为 $f(S)=\prod_{v \in S} w_v$。

对于一种局面，他最终的药水魔法值一定可以写成 $\sum_{S \subseteq U} g_S f(S)$，其中 $g_S \in \{0,1\}$。

而对所有可能的方案求和后，答案一定也可以写成 $\sum_{S \subseteq U} g_S f(S)$。每个数的地位是相同的，所以 $g_S$ 一定只和 $\text{popcount}(S)$ 有关。

因此我们只需要能够算出，每个集合能在多少种方案中得出即可。

考虑 DP。设 $dp_{i,j}$ 表示，全集大小为 $i$，一个大小为 $j$ 的子集能通过多少种方式被合成。我们可以将操作改写成：选择两个药品，丢弃掉一个，或者将他们合并。

我们只能丢弃掉最终不要的药品，以及合并需要的药品。

很容易 $O(n^2)$ 处理出这个东西。

剩下的问题就是：如何求出 $\sum_{S \subseteq U,|S|=i} f(S)$。由于 $f$ 的定义是乘积，这个也很容易用 DP 处理。

总体复杂度 $O(n^2)$，足以通过本题。代码极其短。

注：我最开始用了二十分钟去想 $dp_{i,j}$ 如何转移。因为我思考的主体是“将一种个问题分成两个子问题并且合并”，但是在这道题中完全不适用。

ヾ(｡｀Д´｡)ﾉ彡

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=3000+10; 
int n,ans,a[MAXN],MOD,dp[MAXN][MAXN],mul[MAXN];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>MOD;
	dp[1][1]=1;
	ffor(i,2,n) ffor(j,1,i) dp[i][j]=((i-j)*(i-1)*dp[i-1][j]+j*(j-1)/2*dp[i-1][j-1])%MOD;
	mul[0]=1;
	ffor(i,1,n) {
		cin>>a[i];
		roff(j,n,1) mul[j]=(mul[j]+mul[j-1]*a[i])%MOD;	
	}
	ffor(i,1,n) ans=(ans+mul[i]*dp[n][i])%MOD;
	cout<<ans;
	return 0;
}