luogu#P9345. 夕阳西下几时回

    ID: 13319 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>贪心洛谷原创Special JudgeO2优化构造洛谷月赛

夕阳西下几时回

题目背景

随着夕阳从山间落下,最后一丝余晖逐渐暗淡;美丽的晚霞,终究还是化作一片黑夜。在这番景象中,一阵又一阵的乡愁涌上心头;远离家乡的游子,就算不是病死他乡,又何时能回还?

题目描述

夕阳可以被视作由 nn 种不同颜色组成的一副图,其中第 ii 种的颜色为 aia_i,满足 aa 是长度为 nn 的排列。

定义一个排列的乡愁度为:

  • 对于所有 1in1\le i\le n,记 bi=gcd(ai,ai+1)b_i=\gcd(a_i,a_{i+1})。特别地,我们认为 an+1=a1a_{n+1}=a_1
  • 排列 aa 的乡愁度为序列 bb不同元素的个数。

求是否有一个长度为 nn,乡愁度为 kk 的排列 pp。若有解,请输出任意一个排列。

输入格式

本题有多组测试数据。

第一行一个正整数 TT,表示测试数据组数。

对于每组测试数据,一行两个整数 n,kn,k

输出格式

对于每组测试数据:

  • 如果不存在这样的排列,输出一行一个字符串 No
  • 否则,输出一行一个字符串 Yes,然后输出一行 nn 个正整数 p1,p2,,pnp_1,p_2,\dots,p_n,表示你找到的排列。

校验器忽略字符串大小写,例如,YESyEsyes 都会被视作答案存在。

3
7 1
6 5
11 4

Yes
1 2 3 4 5 6 7
No
Yes
1 11 9 3 6 7 8 2 5 10 4

提示

【提示】

一个长度为 nn 的排列是一个满足 11nn 中的所有正整数恰好出现 11 次的数组。例如,[3,1,2][3,1,2] 是一个长度为 33 的排列,而 [5,5,1,2,3][5,5,1,2,3] 不是一个排列。

【样例 1 解释】

  • 对于第一组数据,b=[1,1,1,1,1,1,1]b=[1,1,1,1,1,1,1],故 pp 的乡愁度为 11
  • 对于第二组数据,可以证明不存在这样的序列。
  • 对于第三组数据,b=[1,1,3,3,1,1,2,1,5,2,1]b=[1,1,3,3,1,1,2,1,5,2,1],包含 44 个不同的元素 — 1,2,31,2,355,故 pp 的乡愁度为 44

【数据规模与约定】

本题采用捆绑测试。

  • Subtask 1(4 points):n9n\le 9n100\sum n\le 100
  • Subtask 2(5 points):k=1k=1
  • Subtask 3(13 points):n200\sum n\le 200
  • Subtask 4(30 points):对于所有测试数据,保证有解。
  • Subtask 5(48 points):无特殊限制。

对于 100%100\% 的数据,1T1051\le T\le 10^53n3×1053\le n\le 3\times 10^51kn1\le k\le nn6×105\sum n \le 6\times 10^5