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

· · 题解

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;
}