C. Moamen and XOR

题目描述：

给你一个n，一个k，a数组中每一个数都小于等于2^k，且a数组所有数进行二进制的与操作得到的结果要大于等于异或的结果，问你这样的a数组能有多少个，对1e9+7取模

思路1之组合数学：

对第 i 位来分析

& >= ⊕分两组情况，& = ⊕ 和 & > ⊕

• & = ⊕

  • & = ⊕ = 1，此时这n个数的第 i 位必然都是1，而要想n个1的⊕为1，n必然为奇数，因为该位全为 1， 则只能贡献这一种情况

  • & = ⊕ = 0，此时至少要出现一个0，且1的个数为偶数，那这个时候的n个第 i 位数，需要偶数个1，

    • n为奇数时$C_{n}^{0} + C_{n}^{2} + C_{n}^{4}...+C_{n}^{n-1}$​,根据二项式定理，他就等于2^n-1
    • 当n为偶数时，不能n个数都是1，也就是不能选$C_{n}^{n}$​,所以等于$C_{n}^{0} + C_{n}^{2} + C_{n}^{4}... + C_{n}^{n-2}$​, 化简后就是2^n-1 – 1

  • 总结一下，当& = ⊕ 时，奇数第 i 位产生的贡献是1 + 2^n-1，第一个1指的是& = ⊕ = 1的那种情况。偶数第 i 位产生的贡献是2^n-1 – 1，最后算ans的时候都得求他们的 k 次方

• & > ⊕

  只能为& = 1，⊕ = 0，也就是全为1

  • n为奇数，显然不可能，因为奇数个1相⊕，只能是1
  • n为偶数，此时第 i 位已经使得& > ⊕,所以 0 到 i 位可以随便取，这里n个数，每个数的第 i 位都有2 种取法，就是2ⁿ种取法，因为有 i 个数都这样，所以就是 (2ⁿ)ⁱ种，但还有一个条件就是第 i + 1到k – 1，这些位的值都相同，而对于每一位，他们能产生的贡献是上面& = ⊕最后一行的2^n-1 – 1，有k – i – 1个数，所以产生的贡献最后乘起来应该是${(2^{n-1} - 1)} ^{k-i-1} * {(2^n)}^i$​​

总的来说，分奇偶：

• 奇数，ans = $(1 + 2^{n-1})^k$
• 偶数，从0开始枚举 i ，ans += ${(2^{n-1} - 1)} ^{k-i-1} * {(2^n)}^i$，枚举结束后再加上$(2^{n-1} - 1)^k$

记得多取点模，可以提前预处理出来2的次方的所有的值，而不是像我这样一直跑快速幂求，会快很多的

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  100000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

ll q_pow(ll a, ll b)
{
    a %= mod;
    ll ans = 1;
    while(b > 0)
    {
        if(b & 1)
        {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int t;
ll n, k;

int main(){
    sd(t);
    while (t--) {
        scanf("%lld%lld", &n, &k);
        if(n & 1){
            ll ans =q_pow(q_pow(2, n - 1) + 1, k);
            cout<<ans<<endl;
        }
        else{
            ll ans = 0;
            for(int i = 0; i < k; ++i){
                ans += 1ll * q_pow(q_pow(2, n - 1) - 1,k - i - 1) * q_pow(q_pow(2, n), i);
                ans %= mod;
            }
            ans += 1ll * q_pow(q_pow(2, n - 1) - 1, k) % mod;
            ans %= mod;
            cout<<ans<<endl;
        }
    }
    return 0;
}

思路2之dp大法好：

dp[i] 表示前 i 位贡献的ans

n为奇数

• 只有两边想等才满足条件，要么为1，要么为0，1只有一种，为0时$(1 + 2^{n-1})$，
• 所以dp[i] = dp[i – 1] * (1 + pow(2, n – 1));

n为偶数

• & = ⊕ = 0，也就是选偶数个1，并删掉全选1的情况，此时dp[i] = dp[i – 1] * (pow(2, n – 1) – 1)
• & = 1, ⊕ = 0, 也就是全选1，此时是不受前 i – 1位的影响的，前 i – 1位可以随便选，也就是dp[i] += pow(pow(2, i – 1), n)
• 故dp[i] = dp[i – 1] * (pow(2, n – 1) – 1) + pow(pow(2, i – 1), n)

dp的最后一个就是我们要的ans

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  100000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

ll q_pow(ll a, ll b){
    a %= mod;
    ll ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int t;
ll n, k;

int main(){
    sd(t);
    while (t--) {
        scanf("%lld%lld", &n, &k);
        if(n & 1){//奇数这里位还是用的第一种写法，因为第二种写法不过就是循环乘起来了，就是个求pow的过程，还不如直接快速幂呢
            ll ans =q_pow(q_pow(2, n - 1) + 1, k);
            cout<<ans<<endl;
        }
        else{
            //dp[i] = dp[i - 1] * (pow(2,n-1) - 1) + pow(pow(2,i-1),n);
            ll tmp = q_pow(2, n - 1) - 1;
            tmp %= mod;
            ll ans = 1;
            for(int i = 0; i < k; ++i){
                ans = (ans * tmp % mod + 1ll * q_pow(q_pow(2, i), n)) % mod;
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}