[数据结构与算法]Codeforces Round #737 (Div. 2) 题解

C Moamen and XOR

题意：

构造一个长度为n的数组，其中第i个元素为a[i]，且对所有的i∈[0,n-1]，满足0=<a[i]<2^k。问有多少种构造方法使得：

a1&a2&a3&…&an≥a1⊕a2⊕a3⊕…⊕an

结果对1e9+7取模。

题解：

按数位去分析，这里先定义几个变量：

1. i：当前位 为从小到大的第i位。
2. AND：所有数的第i位（当前位）相与后的值。
3. XOR：所有数的第i位（当前位）异或后的值。
4. DP[I] :从第0位到i位（即a[x]最多有i位）的所有满足题意的可行方案数。

通过比较AND与XOR会发现有以下4种情况：

1. 1=AND == XOR=1
2. 1=AND > XOR=0
3. 0=AND < XOR=1
4. 0=AND == XOR=0

很明显第1、2、4种情况是使得至少第 i 位能够满足题意的。
但是最终答案只是需要（整体AND）大于（整体XOR）。所以想一想怎么从DP[I-1]转移到DP[i]。（讨论DP[i]时，第i位就当做当前最大位）

首先，初始化DP[-1]=1,接下来根据异或的特性（偶数异或为0，奇数异或等于本身）将n分成奇偶来做说明：

1. 当n为偶数：
   1.1. ????1=AND时，证明所有数最大位位全部为1，那么XOR=偶数个1异或= 0，所以此时AND>XOR。那么转移方程为DP[i] += 2^(n*(i-1)。因为AND最大位大于XOR最大位，那么无论低位是什么样都是满足题意。共有（i-1）位，n个数字，所以方案数位2^(n*(i-1)种。
   1.2 ????0=AND时，证明n个数中至少有一个最大位为0，那么为了满足题目AND>=XOR，那么此时仅考虑AND == XOR == 0的情况（小于的情况不满足题意不考虑）。XOR == 0，则证明有偶数个1，而且不能有n个1（这种情况等于1.1中的讨论方案）,所以能够满足XOR=0的方案数为 c（n,0）+c(n,2)+…+c(n,n-2)种，那么转移方程就是DP[i] += (c（n,0）+c(n,2)+…+c(n,n-2))*dp[i-1] 。 （即：当前可行*之前可行）

2. 当n为奇数:
   2.1 ????1=AND时,证明所有数最大位位全部为1，那么XOR=奇数个1异或= 1，所以此时AND==XOR。那么转移方程为DP[i] += DP[i-1]。因为AND最大位等于XOR最大位，方案数等于低位可行的方案数
   2.2 ????0=AND时，证明n个数中至少有一个最大位为0，那么为了满足题目AND>=XOR，那么此时仅考虑AND == XOR == 0的情况（小于的情况不满足题意不考虑）。XOR == 0，则证明有偶数个0，所以能够满足XOR=0的方案数为 c（n,0）+c(n,2)+…+c(n,n-1)种，那么转移方程就是DP[i] += (c（n,0）+c(n,2)+…+c(n,n-1))*dp[i-1] 。 （即：当前可行*之前可行）

PS：其中计算组合数相加可见代码部分，可自行证明。

代码：

（写法1为题解的思路，写法2思想略微不同，详见代码）
写法1：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 2e5+5;
const int mod = 1e9+7;
int t;
LL n,m,k;
int a[maxn],b[maxn];
int ans = 0;

LL quickpow(LL a,LL b)
{
    LL ret = 1;
    while(b!=0)
    {
        if(b&1)
            ret = (ret*a)%mod;
        a= (a*a)%mod;
        b>>=1;
    }
    return ret;
}

int main()
{
    cin >> t;
    while (t--) 
    {
        cin >> n >> k;
        LL ans = 0;
        LL xs =1;
        LL dp = 1;
        for (int bit = 0; bit <k; ++bit) 
        {
            LL ret = 0;
            if(n%2==0)
            {
                ret = (quickpow(2,bit*n))%mod;
                ret %=mod;
            }
            //组合数计算，写法2同
            LL xs = quickpow(2,n-1);
            if(n%2==0)
                xs--;
            else
                xs++;
            dp = (dp*xs)%mod;
            dp =(dp+ret)%mod;
        }
        ans =dp;
        cout << ans%mod << '\n';
    }
    return 0;
}

写法2（tourist写法）

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 2e5+5;
const int mod = 1e9+7;
int t;
LL n,m,k;
int a[maxn],b[maxn];
int ans = 0;
 
LL quickpow(LL a,LL b)
{
    LL ret = 1;
    while(b!=0)
    {
        if(b&1)
            ret = (ret*a)%mod;
        a= (a*a)%mod;
        b>>=1;
    }
    return ret;
}
 
int main()
{
    io_init;
    cin >> t;
    while (t--) 
    {
        cin >> n >> k;
        LL ans = 0;
        LL xs =1;
        LL dp = 1;
        //与写法一不同的是：写法二是从高位开始判断的，其中dp的含义是保存的是最高的前i位相等的方案数。
        for (int bit = k-1; bit >=0; --bit) 
        {
            if(n%2==0)
            {
            	//直接加入到ans中，高位相等的方案数（dp）*（当前位为1的情况==1）*（低位无所谓的方案数）
                ans += (dp*quickpow(2,bit*n))%mod;
                ans %=mod;
            }
            LL xs = quickpow(2,n-1);
            if(n%2==0)
                xs--;
            else
                xs++;
            //维护高位相等的方案数
            dp = (dp*xs)%mod;
        }
        ans +=dp;
        cout << ans%mod << '\n';
    }
    return 0;
}

后续若再补题，会继续加上。

欢迎指正和评论！