CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 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)$。

<hidden 查看代码>
<code cpp>
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)%Mod;
			_rep(j,1,cnt)
			dp[cnt][j]=(1LL*dp[cnt-1][j]*(1<<pos)+1LL*dp[cnt-1][j-1]*(a[i]%(1<<pos)+1))%Mod;
		}
		else{
			_rep(j,0,cnt)
			dp[cnt][j]=1LL*dp[cnt][j]*(a[i]%(1<<pos)+1)%Mod;
		}
	}
	int ans=0;
	for(int i=k>>pos&1;i<cnt;i+=2)
	ans=(ans+dp[cnt][i])%Mod;
	ans=1LL*ans*inv(1<<pos)%Mod;
	if((cnt&1)==(k>>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;
}
</code>
</hidden>
CVBB ACM Team

用户工具

站点工具

页面工具
