Moamen and XOR

· · 题解

一道计数题

题意

给定 n 和 k ，问有多少个这样的数组，使得

。其中，$a_i$ $\leq$ $2^k$，$\&$ 表示按位与，$\oplus$ 表示按位异或。$n$ $\leq$ $10^6$，答案对 $1e9+7$ 取模。 ### 分析 因为太菜了……所以只想到了个有点麻烦的计数思路。 涉及到二进制上的大小比较，有一个显而易见的字典序性质：大小关系只取决于最高不相同的位置。一旦最高位确定，低位即可任意取值。 根据这个性质就可以计数了。先考虑取大于号的情况。对于第 $i$ 位，如果这 $n$ 个数 $\&$ 起来为 $1$ 且 $\oplus$ 起来为 $0$，那么这 $n$ 个数一定都为 $1$（按位与的性质），且 $n$ 一定为偶数（异或性质），这时对答案的贡献如何计算呢？ 我们将 $i$ 从最高位 $k-1$ 从高到低开始枚举，对于上面这种情况，我们假定枚举过的位按位与和异或答案都为 $0$，未枚举过的位就可以随便取。前面每一位二者都为 $0$ 当且仅当这 $n$ 个数的第 $i$ 个二进制位上有偶数个 $1$，剩余都是 $0$，且不全为 $1$，那么取法就可以表示为： $C_n^0$ $+$ $C_n^2$ $+$ …… $+$ $C_n^{n-2} $ $=$ $2^{n-1}$ $-$ $1

由于还有 k-1-i 位，根据乘法原理，对答案贡献就是

同理计算后面的数，每一位都可以任选，有 $k$ 位，贡献就是 $2^{nk}$。 那么，这一位取大于号对答案的总贡献就是上面两式相乘。每一位累加到答案即可。 算完了大于号，再来算等于号，还是考虑第 $i$ 位，如果他们（$\&$ 和 $\oplus$ 的结果）都是 $1$，那么 $n$ 必为奇数，也就是说，只有 $n$ 为奇数才会出现这种情况。如果他们都是 $0$，那么只需要这 $n$ 个数里有偶数个 $1$ 且不全为 $1$ 即可。与上面的方法同理，简单推导就能得出两者相等对答案的贡献为： $\begin{cases} {(2^{n-1}-1)}^k&\text{ n 为偶}\\ {(2^{n-1}+1)}^k&\text{ n 为奇} \end{cases}

最终答案就是上面两种情况相加。

代码

#include <iostream>
#include <cstdio>

using namespace std;

const int mod = 1e9+7;
const int maxn = 6e5;
typedef long long ll;
ll f[maxn];
ll n, k;

ll ksm(ll a, ll b){
    ll res = 1;
    while(b){
        if(b % 2)
            res = (res * a) % mod;
        b /= 2;
        a = (a * a) % mod;
    }
    return res % mod;
}

int main()
{
    f[0] = 1;
    for(int i = 1; i <= 500000; i++)
        f[i] = f[i-1] * 2ll % mod;
    int T;
    cin >> T;
    while(T--){
        cin >> n >> k;
        ll ans = 0;
        for(ll i = k-1; i >= 0; i--){
            if(n % 2 == 0) ans += ksm(2, n*i) * ksm(f[n-1]-1, k-1-i);
            ans %= mod;
        }
        if(n % 2 == 0) ans += ksm((f[n-1]-1)%mod, k);
        else ans += ksm((f[n-1]+1)%mod, k);
        ans %= mod;
        printf("%lld\n", ans);
    }
    return 0;
}