集合计数

题意：

求 $[0,2^n-1]$内中选择任意数量 (不能不选) 的几个不同的数，它们按位与后有 $k$个 $1$的方案数。

分析：

我们首先定义一个比较容易计算的函数，$g[x]$，以及我们需要求的函数 $f[x]$。$f[x]$表示 “恰有 x 个 1 出现在最终的结果中” 的方案数。

如果我们枚举哪几个位是最终的 $1$，剩下的位情况不确定，这样可以获得。可以得到：
$$
g[x]=C_n^x(2^{(2^{n-x})}-1)
$$
上面这个式子的原理是：包含了这 $x$个 $1$的数字总共有 $2^{n-x}$个，每个都可以选或者不选，但不能一个都不选，因此共 $2^{2^{n-x}}-1$种选法。另外，枚举的这几个 $1$的位置不同，也对应这不同的情况，因此需要乘一个组合数。

但是，$g[x]$并不是一个确切的值，并不是我们常说的 “至少 x 个 1” 的方案数。可以说，它重复计算了很多东西。比如，$011$和 $111$的按位与结果为 $011$，但是这一种情况在 $g[001]$和 $g[010]$中都出现了，因此 $g[2]=g[001]+g[010]$中这种情况出现了两次。不难发现，如果一种情况的按位与结果有 $x$个 $1$，那么它在 $g[y]$中一定出现了 $C_x^y$次。

所以，我们可以直接建立起 $f$和 $g$的关系：
$$
g[x]=\sum_{i=x}^{n}C_i^xf[i]
$$
根据二项式反演：
$$
f[x]=\sum_{i=x}^n(-1)^{i-x}C_i^xg[i]
$$

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define MOD 1000000007
#define MX 1000006

using namespace std;

typedef long long ll;

ll fac[MX], faci[MX], p2i[MX];
int n, k;

ll qpow(ll x, ll t)
{
    ll ans = 1;
    while(t)
    {
        if(t & 1) ans = ans*x%MOD;
        x = x*x%MOD;
        t >>= 1;
    }
    return ans;
}

ll inv(ll x) {return qpow(x, MOD-2);}

ll C(int n, int m) {return fac[n] * faci[m] % MOD * faci[n-m] % MOD;}

ll g[MX];

void init()
{
    fac[0] = 1;
    for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % MOD;
    faci[n] = inv(fac[n]);
    for(int i=n; i>=1; i--) faci[i-1] = faci[i] * i % MOD;
    p2i[0] = 2;
    for(int i=1; i<=n; i++) p2i[i] = p2i[i-1] * p2i[i-1] % MOD;
}

void work()
{
    ll fk = 0;
    for(int i=0; i<=n; i++) g[i] = C(n, i) * (p2i[n-i]-1) % MOD;
    for(int i=k; i<=n; i++)
    {
        if((i^k) & 1) fk = (fk - C(i, k) * g[i]) % MOD;
        else fk = (fk + C(i, k) * g[i]) % MOD;
    }
    printf("%lld\n", (fk+MOD)%MOD);
}

int main()
{
    scanf("%d%d", &n, &k);
    init();
    work();
    return 0;
}