LibreOJ

542 「LibreOJ NOIP Round #1」序列划分

内存限制：512 MB 时间限制：1000 ms

题目描述

梦想从几时开始，命运在何处终结？

有一个长度为 $n$ 的整数序列 ${a_1, a_2, \cdots, a_n}$。

你的任务是判断是否可以将其划分为 $k$ 的倍数个非空子序列，使得每个元素在恰一个子序列中出现，同时每个子序列均以 $k$ 的倍数开头、$k$ 的倍数结尾，并且长度也为 $k$ 的倍数。若能划分，求出任意一个方案。

说明：序列 ${a_1, a_2, \cdots, a_n}$ 的一个子序列是指将任意多个（可以为 $0$ 个）元素删除后，将其他元素按照原序列中的顺序拼接而成的序列。例如，序列 ${9, 8, 5}$、序列 ${7}$ 和序列 ${9, 8, 7, 6, 5}$ 均为序列 ${9, 8, 7, 6, 5}$ 的子序列，但 ${7, 9, 8}$ 不是。

输入格式

输入的第一行包含一个整数 $T$ —— 表示子任务编号（与「数据范围与提示」中编号相同，样例的子任务编号为 $0$）。

第二行包含两个空格分隔的正整数 $n,k$ —— 序列 $a$ 的长度和 $k$ 的值。

第三行包含 $n$ 个空格分隔的正整数 $a_1, a_2, \cdots, a_n$ —— 依次表示序列 $a$ 的元素。

输出格式

若有解，则第一行输出 Yes，否则第一行输出 No。
若有解则按以下格式输出任意一个划分方案：

第二行输出一个整数 $c$ 表示划分成了 $c$ 个子序列，满足 $k\le c\le n$ 且 $c$ 是 $k$ 的倍数；
接下来 $c$ 行每行描述一个子序列：
第 $i$ 行第一个整数 $l_i$ 表示第 $i$ 个子序列的长度，满足 $k\le l_i\le n$ 且 $l_i$ 是 $k$ 的倍数。
接下来 $l_i$ 个整数 $p_{i,1},p_{i,2},\cdots,p_{i,l_i}$ 表示这个子序列中元素的下标。满足 $p_{i,j}<p_{i,j+1}$（即下标单调递增）且 $a_{p_{i,1}}$ 和 $a_{p_{i,l_i}}$ 是 $k$ 的倍数。
另外，$1\sim n$ 中每个数在 $p$ 中出现且仅出现一次。

样例 1

划分为 ${2, 6}$ 和 ${4, 1, 3, 8}$ 两个子序列满足条件。

样例 2

以 $k$ 的倍数结尾什么的最讨厌了 (– ‸– )

样例 3

样例 4

请从页面上方的附加文件中下载。

数据范围与提示

对于所有数据，有 $2 \leq k,n \leq 10^6,0\le a_i\le 10^6$。

Subtask # 分值 $n$ 的限制 $k$ 的限制 特殊限制
1 $5$ $n \le 10$ $k = 2$ -
2 $10$ $n \le 20$ $k \le 20$ -
3 $10$ $n \le 5\times 10^4$ $k = 2$ -
4 $15$ $n \le 10^2$ $k \le 3$ -
5 $10$ $n \le 10^3$ $k \le 10^3$ -
6 $10$ $n \le 5\times 10^4$ $k \le 5\times 10^4$ $a_1,a_2,\cdots ,a_k$ 是 $k$ 的倍数
7 $10$ $n \le 5\times 10^4$ $k \le 5\times 10^4$ 存在方案使得 $a_1$ 和 $a_n$ 属于同一子序列
8 $15$ $n \le 5\times 10^4$ $k \le 5\times 10^4$ -
9 $15$ $n \le 10^6$ $k \le 10^6$ -

样例

样例输入 1

0
6 2
2 4 1 3 6 8

样例输出 1

Yes
2
2 1 5
4 2 3 4 6

样例输入 2

0
6 2
2 4 6 1 3 5

样例输出 2

No

样例输入 3

0
6 2
2 1 2 2 1 2

样例输出 3

Yes
2
4 1 2 5 6
2 3 4

样例输入 4

0
15 3
3 1 1 1 1 3 3 1 3 3 1 1 1 1 3

样例输出 4

Yes
3
6 1 2 3 4 5 10
6 6 11 12 13 14 15
3 7 8 9