时间戳

首页 > 技术文章 > 孤独

孤独

hchhch233 2018-09-26 17:46 原文

Sample Input

2

2 3 4

1 2 3

Sample Output

31

考虑容斥。答案就是{至少满足一个话题的方案数}-{至少满足两个话题的方案数}+{至少满足三个话题的方案数}...

假设一个转态为S（第i位上为1表示满足这个话题），我们就要将所有合法的同学都记下来，设为tot个，则S的方案数就是tot^{k}。

容斥方法与计算方法都非常简单，但关键是如何对每个S求出tot。

我们设满足S的人数为f[S]，我们和显然有2^{n}\cdot m的方法求出f[S]，但肯定T飞。

考虑一个优化一点的做法，对于每个a[i]，我们先将f[a[i]]++，然后f[S]+=\sum _{T\subset S}f[T]。这其实是枚举子

集的方法，时间复杂度大概是3^{n}的，还是不太优秀。

我们发现，对于S枚举所有包含他的集合未免太浪费了，那么我们就枚举包含S的最小的集合，也就是只比S多了一位的集合。

代码如下：

for(int i=1;i<=n;i++) {
	for(int s=(1<<n)-1;s>0;s--) {
		if(s&(1<<i-1)) {
			f[s^(1<<i-1)]+=f[s];
		}
	}
}

注意：这两个循环的顺序不能交换！！

为什么呢？因为交换后会出现重复计算的问题。比如说我们在计算1101对1000的贡献时，如果我们先枚举集合，在枚举转移的位置，就会出现如下图的问题：

1101的贡献就被计算了两次，原因是不同的转移顺序可能得到相同的状态，于是就算重了。

而我们最外层枚举转移顺序就不会出现这样的问题了。

完整代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<ctime>
#define ll long long
#define mod 1000000007
#define M 100005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n,m,k;
ll w[M],cnt[1<<21],f[1<<21],ans;
ll g[1<<21];
int len[1<<21];
ll ksm(ll t,ll x) {
	ll ans=1;
	for(;x;x>>=1,t=t*t%mod)
		if(x&1) ans=ans*t%mod;
	return ans;
}

int Count(int s) {
	int ans=0;
	for(;s;s-=s&(-s)) ans++;
	return ans;
}
int main() {
	Get();
	n=Get(),m=Get(),k=Get();
	for(int i=1;i<=m;i++) {
		w[i]=Get();
		cnt[w[i]]++;
	}
	for(int s=1;s<(1<<n);s++) len[s]=Count(s);
	for(int i=1;i<(1<<n);i++) f[i]=cnt[i];
	for(int i=1;i<=n;i++) {
		for(int s=(1<<n)-1;s>0;s--) {
			if(s&(1<<i-1)) {
				f[s^(1<<i-1)]+=f[s];
			}
		}
	}
	for(int s=1;s<(1<<n);s++) {
		if(len[s]&1) (ans+=ksm(f[s],k))%=mod;
		else ans=(ans-ksm(f[s],k)+mod)%mod;
	}
	cout<<ans;
	return 0;
}

 

推荐阅读