Moamen and XOR（简单dp）

题目 题意：给定n和k，构造元素范围为 [ 0 , 2 k ) [0,2^k) [0,2k)的元素 a i a_i ai​，使得 a 1 & a 2 & . . . a n > = a 1 ⨁ a 2 ⨁ . . . ⨁ a n a_1\&a_2\&...a_n>=a_1 \bigoplus a_2 \bigoplus ... \bigoplus a_n a1​&a2​&...an​>=a1​⨁a2​⨁...⨁an​，求有多少种构造方法。

题解：枚举每一位，dp[i][1]表示元素的前i位的与值大于异或的值，dp[i][0]表示元素的前i位的与值等于异或的值。 dp转移方程为：

dp[i][1] = dp[i][0]*quickp(2,n) + dp[i-1][1]*(全为1时，与值是否大于异或值)
dp[i][0] = dp[i-1][0]*((全为1时，与值是否等于异或值)+(偶数个1的情况数))

初始情况

dp[0][0] = (全为1时，与值是否大于异或值)
dp[0][1] = ((全为1时，与值是否等于异或值)+(偶数个1的情况数))

代码

#include 
using namespace std;
const int maxn = 200010;
#define mod 1000000007 

int n, k, q2, beta;
int dp[maxn][2];
int C[maxn], inv[maxn];

/*
 * 0 = 1;
	}
	return res;
}

void init() {
	inv[0]=1;
    inv[1]=1;
    for (int i = 2; i