【NOIP模拟】孤独

本人太菜，讲不清楚，提供julao同学的PPT

题面

分析

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#define LL long long
using namespace std;
const int MAXN = 100005,MAXM = 100005,MAXK = 100005,MOD = 1e9+7;
int n,m,days,num;
int ok[(1<<20)+5];
LL power(LL a,LL p)
{
    LL v = 1;
    while(p)
    {
        if(p&1)
            v=v*a%MOD;
        a=a*a%MOD;
        p>>=1;
    }
    return v;
}

int main()
{
    scanf("%d%d%d%d",&num,&n,&m,&days);
    for(int i=1;i<=m;i++)
    {
        int v;
        scanf("%d",&v);
        ok[v]++;
    }
    for(int i=0;i<n;i++)
        for(int j = 0;j <(1<<n);j++)
            if(j &(1<<i))
                ok[j^(1 << i)] = (ok[j^(1 << i)]+ok[j])%MOD;
    LL ans = 0;
    for(int i= 1;i<(1<<n);i++)
    {
        int j=0;
        for(int k=0;k<n;k++)
            if(i&(1<<k))
                j++;
        ans=(ans+power(ok[i],days)*((j&1)?1:-1))%MOD;
        ans=(ans+MOD) % MOD;
    }
    printf("%lld
",ans);
    return 0;
}