题解：P9131 [USACO23FEB] Problem Setting P

· · 题解

首先，如果你按照先后关系建图很难做，考虑看成 01 串的包含关系就很清晰了。

这是一个对于子集求和的形式，还是由于可能有多道题目是同一个 01 串，所以对于一种含 i 道题目的 01 串，其系数是 cnt_i=\sum\limits_{j=1}^i{i\choose j}j!。

列出 DP 方程，

dp_s=(\sum\limits_{t\subset s}dp_t+1)\times cnt_{sz_s}

如果没有 cnt_{sz_s} 的系数，我们可以用高维前缀和直接做。有了系数之后，相当于半在线高维前缀和，也就是每求出一个 dp_s 之后，我们都要对其乘以一个数。

考虑到是从子集求和，那么有 |t|<|s|，我们直接先枚举集合大小，然后按照集合大小分层转移，当前层由之前层的高维前缀和转移而来，而当前层做完之后，每个数乘以相应系数之后，层内来一个高维前缀和即可。

时间复杂度 O(m^22^m)。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=(1<<20)+2;
const int mod=1e9+7;
void add(int &x,int y){ x=x+y>=mod?x+y-mod:x+y; }
void sub(int &x,int y){ x=x<y?x-y+mod:x-y; }
int n,m,a[maxn],pc[maxn]; vector<int> vec[maxn]; char s[maxn];
int cnt[maxn],sum[maxn],f[maxn],fac[maxn],ifac[maxn],g[maxn];
int qpow(int x,int k){
    int res=1;
    for(;k;k>>=1){
        if(k&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod;
    }
    return res;
}
int A(int x,int y){ return 1ll*fac[x]*ifac[x-y]%mod; }
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m; fac[0]=ifac[0]=1;
    for(int i=1;i<=m;i++){
        cin>>(s+1);
        for(int j=1;j<=n;j++)
            if(s[j]=='H') a[j]+=(1<<i-1);
    }
    for(int i=1;i<=n;i++) fac[i]=1ll*i*fac[i-1]%mod;
    for(int i=1;i<=n;i++) ifac[i]=qpow(fac[i],mod-2);
    for(int i=1;i<=n;i++) cnt[a[i]]++;
    swap(n,m);
    for(int s=0;s<(1<<n);s++){
        if(s) pc[s]=pc[s^(s&-s)]+1;
        vec[pc[s]].pb(s);
        for(int j=1;j<=cnt[s];j++)
            add(g[s],A(cnt[s],j));
    }
    for(int i=0;i<=n;i++){
        for(int s=0;s<(1<<n);s++) f[s]=0;
        for(auto s:vec[i]) f[s]=1ll*(1+sum[s])*g[s]%mod;
        for(int j=1;j<(1<<n);j<<=1)
            for(int s=0;s<(1<<n);s++)
                if(s&j) add(f[s],f[s^j]);
        for(int s=0;s<(1<<n);s++) add(sum[s],f[s]);
    }
    cout<<sum[(1<<n)-1];
    return 0;
}