Warning: session_start(): open(/tmp/sess_c69813f54d2f200a7c5aa621cb915544, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== CCPC Wannafly Camp Day2 ======
[[https://ac.nowcoder.com/acm/contest/4010|比赛链接]]
===== B. 萨博的方程式 =====
==== 题意 ====
给定方程 $x_1\oplus x_2\oplus \cdots x_n =k$。
其中限定 $x_i\le m_i$，问方程的解的个数。
==== 题解 ====
不妨设 $m=\max(m_1,m_2\cdots m_n)$，且 $m$ 的最高位是第 $y$ 位。
假设 $\text{dp}(i,j)$ 表示前 $i$ 个数有 $j$ 个数第 $y$ 位为 $1$ 时 $(x_1,x_2\cdots x_i)$ 的取值方案数。
于是若 $m_i$ 第 $y$ 位为 $1$，分别考虑 $x_i$ 第 $y$ 位为 $0$ 和为 $1$ 的情况，有
$$
\text{dp}(i,j)\gets 2^y\text{dp}(i-1,j)+(m_i\bmod 2^y)\text{dp}(i-1,j)
$$
若 $m_i$ 第 $y$ 位为 $0$，有
$$
\text{dp}(i,j)\gets (m_i\bmod 2^y)\text{dp}(i-1,j)
$$
设 $m_i$ 中有 $\text{cnt}$ 个数第 $y$ 位为 $1$，接下来我们考虑 $\text{dp}(n,i)(0\le i\le \text{cnt})$ 对答案的贡献。
首先，如果 $k$ 第 $y$ 位为 $0$，则 $i$ 的必须是偶数，如果 $k$ 第 $y$ 位为 $1$，则 $i$ 的必须是奇数。
接下来对所有合法的 $i$，$x_1\oplus x_2\oplus \cdots x_n$ 的第 $y$ 位一定与 $k$ 相同，接下来只需要考虑前 $y-1$ 位。
假如 $i=\text{cnt}$ 合法，则这等价于所有 $x$ 的第 $y$ 位已经确定，于是可以忽略 $m_i$ 和 $k$ 的 $y$ 位，问题转化为原题的子问题。
接下来考虑剩下所有合法的 $i\neq \text{cnt}$，由于 $i\lt \text{cnt}$，于是至少有一个 $x_j$ 满足 $x_j$ 第 $y$ 位不等于 $1$ 且 $m_j$ 第 $y$ 位等于 $1$。
于是 $x_j$ 的前 $y-1$ 位无限制。固定其他所有 $x$，对 $x_j\in [0,2^y-1]$，恰有一个 $x_j$ 使得 $x_1\oplus x_2\oplus \cdots x_n =k$。
于是此时 $i$ 对答案的贡献为 $\frac {\text{dp}(n,i)}{2^y}$。总时间复杂度 $O(n^2\log m)$。
ps. $\text{dp}(i,j)$ 实际上可以换成 $\text{f}(i)=\sum_{j=0,2\mid j}\text{dp}(i,j),\text{g}(i)=\sum_{j=1,2\not\mid j}\text{dp}(i,j)$ 维护，时间复杂度降为 $O(n\log m)$。
const int MAXN=55,Mod=1e9+7;
int n,k;
int a[MAXN],dp[MAXN][MAXN];
int inv(int a){
int ans=1,k=Mod-2;
while(k){
if(k&1)ans=1LL*ans*a%Mod;
a=1LL*a*a%Mod;
k>>=1;
}
return ans;
}
int cal(int pos){
if(pos<0)return 1;
dp[0][0]=1;
_for(i,1,MAXN)dp[0][i]=0;
int cnt=0;
_for(i,0,n){
if((a[i]>>pos&1)==1){
cnt++;
dp[cnt][0]=1LL*dp[cnt-1][0]*(1<>pos&1;i>pos&1))
ans=(ans+cal(pos-1))%Mod;
return ans;
}
int main()
{
while(~scanf("%d%d",&n,&k)){
_for(i,0,n)a[i]=read_int();
enter(cal(30));
}
return 0;
}