Atcoder Beginner Contest 150

$A,B,C$

签到题,随便做做。

$D$

将每一个数里面的 $2$ 全部提出来,其个数即为 $w_i$ ,如果 $w$ 不是所有数都相等,那么无解。

否则求出所有数的 $lcm$ ,再乘上 $2^{w_i-1}$ ,剩下的一个 $2$ 放入 $(p+0.5)$ 中,可以看出这一定是个奇数。

答案就是 $[1,M]$ 中 $lcm$ 的倍数,且为奇数的数的个数。

注意一点,如果 $lcm$ 超过 $M$ ,立刻退出并输出 $0$ ,不然会爆 $long\ long$ (虽然并没有卡)。

$E$

首先,我们有一个贪心的想法:权值更小的应该更先修改

这一点可以用微扰法轻松证明。

我们将 $C$ 排序,然后依次考虑每一位的贡献。

我们有这样一个式子:

表示之前的所有位已经修改,所以可能的情况有 $2^{2\cdot (i-1)}$ 种。

这一位要修改,有 $2$ 种情况。

最后的 $n-i$ 位,无论是每一位无论是相同还是不同,都是需要确定其中一排即可,方案数为 $2^{n-i}$ 。

在之后的 $n-i$ 位中,我们枚举有 $k$ 对不一样的,一共有 $\binom{n-i}{k}$ 种可能,每种会带来 $k+1$ 的贡献。

前面的好处理,主要是后面的组合数的问题。

但是我们有两个很好的结论:

然后我们将 $k+1$ 的括号拆开,就行了。

最后化简得到的结果是:

$F$

比赛的时候没时间做了,看了下,做法比较显然。

我们按照每一位来考虑。

首先枚举 $k$ ,因为所有 $a’_i\ XOR\ k=b_i$ ,我们有 $a’_i\ XOR\ b_i=k$ 。

所以我们需要 $a’$ 和 $b$ 异或起来相等。

那么在每一位上,我们都有一个 $01$ 数列,要想要相等,每一位都必须是完全相等或者完全相反,这个我们可以用原数列的 $hash$ 和取反后的数列的 $hash$ 快速求出。