题解：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)

。

CPP

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

题解：P9131 [USACO23FEB] Problem Setting P

文章操作

相关推荐

评论

题解：P9131 [USACO23FEB] Problem Setting P