题目背景
他说,如果破茧之后发现自己并不是蝴蝶,而是一只难看的蛾子,那该怎么办?
——题记
题目描述
给定一个长度为 2n 的二进制序列 a,该序列由 0 和 1 组成。最初序列的所有元素均为 0。你的任务是对该序列执行 q 次操作:
- 翻转操作:对于给定的下标 i,翻转 ai(即将 ai 变为 1−ai)。该操作表示为
! i
。 - 查询操作:对于给定的下标 i,确定所有满足 j⊆i 的 aj 中,1 的个数是奇数还是偶数。这里 j⊆i 意味着在 i 和 j 的二进制表示中,j 中所有为 1 的位在 i 中对应的位也必须是 1。该操作表示为
? i
。
输入格式
第一行包含两个整数 n 和 q,表示序列的长度为 2n,接下来有 q 个操作。
接下来的 q 行,每一行表示一个操作,可以是以下两种形式之一:
! i
表示一个翻转操作。? i
表示一个查询操作。
输出格式
对于每个查询操作 ? i
,输出一个整数:
- 如果满足条件的 aj 中 1 的个数为奇数,输出 1。
- 如果 1 的个数为偶数,输出 0。
样例 1
样例 1 输入
4 10
! 4
? 15
! 2
? 12
! 8
! 5
? 10
? 7
? 13
? 15
样例 1 输出
1
1
0
1
1
0
样例 2
样例 2 输入
32 10
! 772
! 34373648
? 4286562043
? 3890741199
! 18874880
! 269484552
! 1122312
? 4277131259
! 104867841
? 3087007739
样例 2 输出
1
1
1
1
附加样例 1~100
见附件下载中的 ex_subset1~100.in
与 ex_subset1~100.out
。
是的,你没有看错 (@^◡^)
数据范围
子任务编号 | 子任务分值 | 测试点个数 | n= | q= | 特殊性质 |
---|---|---|---|---|---|
1 | 10 | 8 | 24 | 106 | 无 |
2 | 10 | 8 | 26 | 106 | 无 |
3 | 10 | 8 | 28 | 106 | 无 |
4 | 10 | 8 | 30 | 106 | 无 |
5 | 10 | 8 | 32 | 106−10 | 数据随机生成 |
6 | 50 | 20 | 32 | 106 | 无 |
对于子任务 5,数据按照下面的规则随机生成,其中所有的随机事件彼此独立:
- 每个操作有 50% 的概率是翻转操作或查询操作。
- 翻转操作下标的每一个二进制位有 70% 的概率为 0,有 30% 的概率为 1。
- 查询操作下标的每一个二进制位有 70% 的概率为 1,有 30% 的概率为 0。
计分规则
假设该测试点属于一个分值 S 分的子任务:
你的输出会逐行与正确输出进行比较。如果你的输出完全正确,你将获得 S 分。否则,如果你的输出第一次出现错误是在第 x 个操作,将使用公式 ⌊x−1q/S⌋ 来计算得分。换句话说,每完整处理 q/S 次操作,你就获得 1 分。
每个子任务的最终得分为其所有测试点中的最低得分。各个子任务之间相互独立,不存在任何依赖关系。