Luogu 2018 11月月赛 T3(状压DP+组合数学)

题意:要从$000…000$变换到$111…111$, 变换过程可以选择一个全$0$子集来改成$1$。然后每次改完出现什么状态如果在给出的状态中,就加上这个权。求所有可能变换的总权。

容易想到$dp(S)$为到$S$状态的总权,则$dp(S)=\sum dp(S-sonS)+num(S) \cdot w(S)$,其中$w$为状态权,$num$为有多少个状态转移到这个状态。枚举子集即可。时间复杂度$O(\sum C^k_n \cdot 2^k)$,由二项式定理,时间复杂度为$O(3^n)$

上面能拿$ 70 $分。我们想想这个$ dp $其实没必要。
我们可以考虑每个状态对答案的贡献。发现每个$1​$数量相等状态其实本质一样。所以我们只需要考虑不同数量$1​$的贡献即可。显然若设$cnt(x)​$为$x​$个$1​$的贡献次数,则

$$cnt(x)=\sum^{i-1}_{i=0} C^i_x cnt(x-i)$$

然后答案是$ans=\sum cnt(num_1)cnt(num_0)$, $num_x$即为二进制下为$x$的个数。

1、状态转移画成 DAG 更好。状态不画多个点,这样方便找规律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define LL long long
#define db double
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
namespace flyinthesky {
const LL MO = 998244353;
int n, m, st[(1 << 20) + 5];
LL dp[(1 << 20) + 5], num[(1 << 20) + 5];
char s[25];
void clean() {
ms(num, 0);
}
int solve() {
scanf("%d%d", &n, &m);
clean();
for (int v, i = 1; i <= m; ++i) {
scanf("%s%d", s, &v);
int tmp = 0;
for (int j = 0; j < n; ++j) tmp += (1 << (n - j - 1)) * (s[j] - '0');
st[tmp] = v;
}
// for (int i = 0; i < (1 << n); ++i) cerr << i << " " << st[i] << endl;
dp[0] = st[0], num[0] = 1ll;
for (int S = 1; S < (1 << n); ++S) {
for (int i = S; i; i = (i - 1) & S) {
dp[S] = (dp[S] + dp[S - i]) % MO;
num[S] = (num[S] + num[S - i]) % MO;
}
dp[S] = (dp[S] + num[S] * st[S]) % MO;
}
printf("%lld\n", dp[(1 << n) - 1]);
return 0;
}
};
int main() {
flyinthesky::solve();
return 0;
}
------ 本文结束 ------