5862. 【NOIP2018提高组模拟9.9】孤独(容斥)
程序员文章站
2022-03-31 08:08:14
...
题目大意:
思路:
这题十分的有意思,考虑经典容斥,答案=选择第一个话题能交流的人数的k次方+选择第二个话题交流的人数的k次方+….-选择一二两个话题都能交流的人数的 k 次方+…
复杂度为m*2^n。发现我们每次转移m的复杂度太高了,我们考虑去怎么优化他的转移,观察可得这是个子集问题,设一个dp[i],为i子集的方案数,就等于他所有的父亲加起来。这样子优化到了o(n*2^n)
程序:
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 2000000
#define mo 1000000007
#define LL long long
using namespace std;
LL ans;
int n,m,k,x,s[N],hjy[N];
LL mul(LL x,LL y){
if (y==1) return x;
LL o=mul(x,y/2);
o=(o*o)%mo;
if (y%2==1) o=(o*x)%mo;
return o;
}
inline void dfs(int x,int dep){
if (dep==n) {
int o=x,p=0;
while (o){
if (o%2==1) p++;
o>>=1;
}
if (p==0) return;
if (p%2==0) ans=(ans-mul(s[x],k)+mo)%mo;
else ans=(ans+mul(s[x],k))%mo;
return;
}
dfs((x<<1)+1,dep+1);
dfs(x<<1,dep+1);
}
int main(){
freopen("a.in","r",stdin);
// freopen("loneliness.in","r",stdin);
// freopen("loneliness.out","w",stdout);
scanf("%d",&x);
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=m;i++) {
scanf("%d",&x);
s[x]++;
}
for (int i=0;i<n;i++)
for (int j=1;j<=(1<<(n+1)-1);j++) if (j&(1<<i)) s[j^(1<<i)]+=s[j];
dfs(0,0);
printf("%lld",ans);
}