欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

5862. 【NOIP2018提高组模拟9.9】孤独(容斥)

程序员文章站 2022-03-31 08:08:14
...

题目大意:

5862. 【NOIP2018提高组模拟9.9】孤独(容斥)

思路:

这题十分的有意思,考虑经典容斥,答案=选择第一个话题能交流的人数的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);
}
相关标签: 何嘉阳