QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 512 MB Total points: 100

# 5176. 多控制反转

Statistics

平面上有 $m$ 个 01 变量,编号依次为 $0,1,\dots,m-1$,你并不知道这些变量的初始值。

你可以进行若干种操作:

单点反转,形如 1 x,表示把编号为 $x$ 的 01 变量反转(0 变成 1,1 变成 0)。

单控制反转,形如 2 x y(你需要保证 $x\ne y$),表示,假如进行操作时编号为 $x$ 的 01 变量值为 1,那么把编号为 $y$ 的 01 变量反转;否则什么都不干。

双控制反转,形如 3 x y z(你需要保证 $x,y,z$ 两两不同),表示,假如进行操作时编号为 $x$ 和编号为 $y$ 的 01 变量值都为 1,那么把编号为 $z$ 的 01 变量反转;否则什么都不干。

现在给定你 $n,Q$,其中 $n$ 是一个小于 $m$ 的非负整数,你需要构造一个长度不超过 $Q$ 的操作序列,使得对于这 $m$ 个 01 变量所有可能的初始值,满足:

假如编号为 $0,1,\dots,n-1$ 的 01 变量初始值都为 1 时,在依次执行完操作序列里的操作后,编号为 $n$ 的 01 变量会反转,而其他变量值都和初始一致。

假如编号为 $0,1,\dots,n-1$ 的 01 变量初始值不全为 1 时,在依次执行完操作序列里的操作后,所有变量值都和初始一致。

注意:显然我们不可能用所有 $2^m$ 种情况都对你构造的操作序列进行检查,在真实测试中,对于每个测试点,我们会选取一部分可能的初始情况进行检查,设这些情况构成的集合为 $T$,你只需要保证你构造的操作序列在 $T$ 内的所有情况满足条件即可。

输入格式

第一行四个正整数 $n,m,Q,case$。其中 $n,m,Q$ 含义与题目描述中相同,$case$ 是该数据所在子任务的编号。特别的,如果 $case=0$,说明这是样例数据。

输出格式

第一行一个整数 $k$,表示你构造的操作序列长度,你需要保证 $0\le k\le Q$。

接下来 $k$ 行,对于第 $i$ 行,先输出一个整数 $ty\in\{1,2,3\}$ 表示第 $i$ 个操作的操作类型,然后输出 $ty$ 个数表示该操作涉及的变量编号,格式参见题面。

样例

样例输入 1

3 5 25 0

样例输出 1

4
3 0 1 4
3 2 4 3
3 0 1 4
3 2 4 3

枚举所有初始情况即可检验该方案正确性。

数据范围

子任务编号 $n \le$ $Q=$ $m=$ 特殊限制 子任务分数 子任务依赖
$1$ $20$ $8n+1$ $2n+2$ A $15$ $ $
$2$ $50$ $10$ $1$
$3$ $ $ $10$ $2$
$4$ $20$ $n^2+1$ $n+2$ A $10$ $ $
$5$ $ $ $20$ $4$
$6$ $50$ $28n+1$ $ $ $10$ $ $
$7$ $100$ $8n+1$ A $10$ $2,4$
$8$ $ $ $15$ $3,5,6,7$

特殊限制A:$\forall (x_0x_1\dots x_{m-1})\in T$,保证 $x_{n+1}=x_{n+2}=\dots=x_{m-1}=0$。

对于所有数据,保证 $0\le n\le 100,m\ge n+2,Q\ge 8n+1$。

时间限制:5s

空间限制:512 MB