ARC 115 题解
A先将其压成二进制数,考虑两个人 $(i,j)$ 他们不可能拥有相同的通过数当且仅当它们不同的位的数量是奇数,也就是 $x\text{ xor } y$ 有奇数个 $1$。然后我赛时直接冲了个 FWT 过了稍微分析一下,发现两个数不同,当且仅当一个是 $1$ 一个是 $0$,我们只考虑这些不同的位置,发现恰好一个 $1$ 的数量是奇数一个是偶数。反过来也是对的。所以统计一下有奇数个 $1$ ...
A先将其压成二进制数,考虑两个人 $(i,j)$ 他们不可能拥有相同的通过数当且仅当它们不同的位的数量是奇数,也就是 $x\text{ xor } y$ 有奇数个 $1$。然后我赛时直接冲了个 FWT 过了稍微分析一下,发现两个数不同,当且仅当一个是 $1$ 一个是 $0$,我们只考虑这些不同的位置,发现恰好一个 $1$ 的数量是奇数一个是偶数。反过来也是对的。所以统计一下有奇数个 $1$ ...
A把 $b$ 都提到最前面就好了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back...
E题意有一个随机数生成器,生成 $[0,n-1]$ 之内的数,生成第 $i$ 个数的概率为 $\frac{A_i}{S}$,其中 $S=\sum_{i=1}^n A_i$。当 $\forall i \in [0,n-1]$ $i$ 被生成至少 $B_i$ 次时停止生成,求期望生成次数,对大质数取模。题解设第 $i$ 个数最后一次被随机到的时间为 $t_i$,答案就是 $\max t_i$ 的...