| 题目名称 | 2681. k次按位异或 |
|---|---|
| 输入输出 | k_xor.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 FoolMike
于2017-04-28加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：8， 提交：13， 通过率：61.54% | ||||
 AntiLeaf |
100 | 0.422 s | 0.82 MiB | C++ |
 _Itachi |
100 | 0.593 s | 0.79 MiB | C++ |
|
_Itachi |
100 | 0.600 s | 0.79 MiB | C++ |
 再见 |
100 | 0.770 s | 1.29 MiB | C++ |
 梦那边的美好ET |
100 | 1.047 s | 14.66 MiB | C++ |
 shy |
100 | 1.512 s | 2.17 MiB | Pascal |
 FoolMike |
100 | 2.575 s | 4.29 MiB | C++ |
 kito |
100 | 5.526 s | 8.29 MiB | C++ |
|
_Itachi |
0 | 0.528 s | 0.79 MiB | C++ |
|
_Itachi |
0 | 0.621 s | 0.79 MiB | C++ |
| 关于 k次按位异或 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
TLE那个是VFK论文里提到的分治乘法+快速幂，AC的那个是FWT。
话说FWT和FFT写的挺像的嘛…… 哪位神犇写分治乘法+快速幂卡过的一定要发帖公开代码，让我等Orz，我写的得1.2s。 | ||||
【题目描述】
给出 $n$ 个整数 $a_i$，从中选出 $k$ 个（可以重复），接下来有 $Q$ 个询问，每次给出一个整数 $x$，表示有多少种方案，使得选出的 $k$ 个按位异或等于 $x$。两种方案不同当且仅存在一个 $j$，使得选择的第 $j$ 个数的下标不同。方案数对 $10007$ 取模。
【输入格式】
第一行两个整数 $n$ 和 $k$;
第二行 $n$ 个正整数，表示 $a_i$;
接下来一个整数 $Q$;
接下来一行 $Q$ 个整数 $x$，整数均非负。
【输出格式】
$Q$ 行，每行一个整数，表示该次询问的答案。
【样例输入】
4 3 1 2 3 1 7 0 1 2 3 4 5 6
【样例输出】
12 20 16 16 0 0 0
【数据规模】
$n,q \leq 1e5，a_i,x \leq (1<<17)，k \leq 1e9$。
【来源】
Mike位运算题组T6