Codeforces Round #737 (Div. 2) C.Moamen and XOR_codeforces round #737 (div. 2) c - moamen and xor

题目链接：C.Moamen and XOR
题目大意：
一个含有n个数的数组，每个数都要满足小于2的k次方，求满足a1 &a2&a3&…&an≥a1⊕a2⊕a3⊕…⊕an.的个数
思路：
k<=2e5,再加上题中的位运算符号，很自然的想到用二进制来表示数组中的每一个数以及最终的结果，我们一位一位分析，设前一个式子为A，后一个式子为B，则可画出以下表格

显然我们要分奇偶讨论，并且从低位向高位枚举，当枚举到某一位时，他的高位全部设为0，并设ans[i]表示0~i位一共有多少种满足题意的情况
当n为偶数时：
$$\begin{gathered} 当A的第k位为1,B的第k位为0时，此时n个数的 \\ 第k位有1种情况，n个数的0到k-1位有2^{(n\ast (k-1))}种情况 \end{gathered}$$
即

ans[i] = (ans[i] + quick_pow(2,n*(i-1),mod)) % mod;
1

当A的第k位为1,B的第k位为0时，n一定是奇数，不符合大条件。

当A的第k位为0,B的第k位为0时，此时n个数的第M位有1种情况,$$(M=C_n^0+C_n^2+\dots \dots +C_n^{(n-2)}=2^{(n-1)}-1)$$
，0~k-1位有ans[i-1]种情况即

ans[i] = (ans[i] + (ans[i - 1]) * (quick_pow(2,n-1,mod)-1)) % mod;
1

当n为奇数时：
当A的第k位为1,B的第k位为0时，n一定是偶数，不符合大条件。

当A的第k位为0,B的第k位为1时，不满足题意。

当A的第k位为1,B的第k位为1时，此时n个数的第k位有1种情况，0~k-1位有ans[i-1]种情况，即

ans[i] = (ans[i] + ans[i - 1]) % mod。
1

当A的第k位为0,B的第k位为0时，此时n个数的第M位有1种情况,$$M=C_n^0+C_n^2+\dots \dots +C_n^{(n-1)}=2^{(n-1)}$$
即

ans[i] = (ans[i] + (ans[i - 1]) * (quick_pow(2,n-1,mod)% mod)) % mod;
1

code:

#include <bits/stdc++.h>
#define DEBUG freopen("_in.txt", "r", stdin);
// #define DEBUG freopen("_in.txt", "r", stdin), freopen("_out.txt", "w", stdout);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll maxn = 3e5 + 10;
const ll maxm = maxn * 2;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = 3.1415926;
const ll mod = 1e9 + 7;

ll res[maxn], ans[maxn];

ll quick_pow(ll a,ll b,ll MOD)
{
    ll ans=1,base=a;
    while(b!=0)
    {
        if(b&1) ans=ans%MOD*base%MOD;
        base=base%MOD*base%MOD;
        b>>=1;
    }
    return ans%MOD;
}

int main()
{
    // DEBUG;
    ll T;
    scanf("%lld", &T);
    while (T--)
    {
        ll n, k;
        memset(res, 0, sizeof(res));
        memset(ans, 0, sizeof(ans));
        scanf("%lld%lld", &n, &k);
        ans[0]=1;
        for (ll i = 1; i <= k; i++)
        {
            if (n % 2 == 0)
            {
                ans[i] = (ans[i] + quick_pow(2,n*(i-1),mod)) % mod;
                ans[i] = (ans[i] + (ans[i - 1]) * (quick_pow(2,n-1,mod)-1)) % mod;
            }
            else
            {
                ans[i] = (ans[i] + ans[i - 1]) % mod;
                ans[i] = (ans[i] + (ans[i - 1]) * (quick_pow(2,n-1,mod)% mod)) % mod;
            }
        }
        printf("%lld\n",ans[k]);
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57