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

JZOJ5862. 【NOIP2018提高组模拟9.9】孤独

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

JZOJ5862. 【NOIP2018提高组模拟9.9】孤独
JZOJ5862. 【NOIP2018提高组模拟9.9】孤独

题解

根据容斥原理,答案就应该是每个话题的方案数,减去两个话题的方案数,加上三个话题的方案数,再减去四个话题的方案数,…
分析一下复杂度,计算枚举话题的方案数乘上每次统计当前这种话题的方案数O(2nm
这个会时间超限,关键就是在统计方案数。
一个数,如果对某个方案贡献,就是这个数是它的子集,
考虑一种更加优秀的枚举子集办法。

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;
}
相关标签: 容斥原理