JZOJ5862. 【NOIP2018提高组模拟9.9】孤独
程序员文章站
2022-03-31 08:08:20
...
题解
根据容斥原理,答案就应该是每个话题的方案数,减去两个话题的方案数,加上三个话题的方案数,再减去四个话题的方案数,…
分析一下复杂度,计算枚举话题的方案数乘上每次统计当前这种话题的方案数O()
这个会时间超限,关键就是在统计方案数。
一个数,如果对某个方案贡献,就是这个数是它的子集,
考虑一种更加优秀的枚举子集办法。
code
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <time.h>
#define ll long long
#define N 100003
#define M 23
#define db double
#define P putchar
#define G getchar
#define inf 998244353
#define pi 3.1415926535897932384626433832795
using namespace std;
char ch;
void read(int &n)
{
n=0;
ch=G();
while((ch<'0' || ch>'9') && ch!='-')ch=G();
ll w=1;
if(ch=='-')w=-1,ch=G();
while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
n*=w;
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
ll abs(ll x){return x<0?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>9) write(x/10);P(x%10+'0');}
const int mo=1000000007;
int z[M],a[N],g[1048576],n,m,k,x,y;
ll ans;
ll ksm(ll x,int y)
{
ll s=1;
for(;y;y>>=1,x=x*x%mo)
if(y&1)s=s*x%mo;
return s;
}
void add(ll& x,ll y){x=(x+y>=mo?x+y-mo:x+y);}
void dg(int x,int y,int t)
{
add(ans,(t&1)?ksm(g[y],k):(mo-ksm(g[y],k)));
if(g[y]==0)return;
for(int i=x+1;i<=n;i++)
dg(i,y|z[i-1],t^1);
}
int main()
{
freopen("loneliness.in","r",stdin);
freopen("loneliness.out","w",stdout);
z[0]=1;for(int i=1;i<M;i++)z[i]=z[i-1]<<1;
read(n);
read(n);read(m);read(k);
for(int i=1;i<=m;i++)
for(read(x),y=x;x;x=(x-1)&y)g[x]++;
for(int i=1;i<=n;i++)
dg(i,z[i-1],1);
printf("%lld",ans);
return 0;
}