「KDOI-04」XOR Sum

Luogu

IDLGP9033

Time2000ms

Memory512MB

DifficultyP2

洛谷原创Special JudgeO2优化构造洛谷月赛

给定一个正整数 $n$，请构造一个长度为 $n$ 的**非负整数**序列 $a_1,a_2,\dots,a_n$，满足： + 对于所有 $1\le i\le n$，都有 $0\le a_i\le m$。 + $a_1\oplus a_2\oplus\dots\oplus a_n=k$。其中 $\oplus$ 表示[按位异或](https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677)运算。或者判断不存在这样的序列。 ## Input **本题包含多组测试数据。** 输入的第一行包含一个正整数 $T$，表示测试数据组数。对于每组测试数据，输入包含一行三个非负整数 $n,k,m$。 ## Output 对于每组测试数据，输出一行一个 $-1$ 表示没有这样的序列存在。否则，输出 $n$ 个用空格分隔的**非负整数**，表示你所构造的序列。如果有多个合法的答案，你只需要输出其中任意一种。 [samples] ## Background 凯文一眼秒了这题。 ![](https://cdn.luogu.com.cn/upload/image_hosting/lh1xvu75.png) ## Note **【样例解释】** 对于第 $1$ 组测试数据，有且仅有一个序列满足条件。对于第 $2$ 组测试数据，由于 $4\oplus 7=3$ 且 $4,7\le10$，所以这是一个合法的答案。同样地，序列 $(2,1)$ 也是一个合法的答案。对于第 $4$ 组测试数据，可以证明不存在满足要求的序列。 **【数据范围】** 记 $\sum n$ 为单个测试点中所有 $n$ 的值之和。对于所有测试数据，保证 $1\le T\le 1~000$，$1\le n\le 2\cdot10^5$，$0\le m,k\le 10^8$，$\sum n\le 2\cdot10^5$。 **【子任务】** **本题开启捆绑测试。** + Subtask 1 (18 pts)：$k\le m$。 + Subtask 2 (82 pts)：没有额外的约束条件。

Samples

Input #1

5
1 2 2
2 3 10
2 11 8
20 200000 99999
11 191 9810

Output #1

2 
4 7 
8 3 
-1
191 191 191 191 191 191 191 191 191 191 191

API Response (JSON)

{
  "problem": {
    "name": "「KDOI-04」XOR Sum",
    "description": {
      "content": "给定一个正整数 $n$，请构造一个长度为 $n$ 的**非负整数**序列 $a_1,a_2,\\dots,a_n$，满足： + 对于所有 $1\\le i\\le n$，都有 $0\\le a_i\\le m$。 + $a_1\\oplus a_2\\oplus\\dots\\oplus a_n=k$。其中 $\\oplus$ 表示[按位异或](https://baike.baidu.com/item/%E5%BC",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9033"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个正整数 $n$，请构造一个长度为 $n$ 的**非负整数**序列 $a_1,a_2,\\dots,a_n$，满足：\n\n+ 对于所有 $1\\le i\\le n$，都有 $0\\le a_i\\le m$。\n+ $a_1\\oplus a_2\\oplus\\dots\\oplus a_n=k$。其中 $\\oplus$ 表示[按位异或](https://baike.baidu.com/item/%E5%BC...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments