梦想从几时开始,命运在何处终结?
有一个长度为 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。 若有解则按以下格式输出任意一个划分方案:
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 中出现且仅出现一次。
0 6 2 2 4 1 3 6 8
Yes 2 2 1 5 4 2 3 4 6
划分为 \{2, 6\} 和 \{4, 1, 3, 8\} 两个子序列满足条件。
0 6 2 2 4 6 1 3 5
以 k 的倍数结尾什么的最讨厌了 (– ‸– )
0 6 2 2 1 2 2 1 2
Yes 2 4 1 2 5 6 2 3 4
0 15 3 3 1 1 1 1 3 3 1 3 3 1 1 1 1 3
Yes 3 6 1 2 3 4 5 10 6 6 11 12 13 14 15 3 7 8 9
请从页面上方的附加文件中下载。
对于所有数据,有 2 \leq k,n \leq 10^6,0\le a_i\le 10^6 。