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 更好。状态不画多个点，这样方便找规律。

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