给定nk,构造一个1-n的排列P,满足对于1-n中的每个i,P都存在一个长为i的子序列,并且每个子序列的和模n都余k.有解则输出任意P,无解输出-1.
首先考虑判断解存在的问题.根据题意,因为P也是自己的子集,所以一定也应该满足"所有元素的和模n余k"的题设,也就是sum(1~n)%n==k,如果不满足,那自然无解.
假设k满足上述条件,接下来的命题就是判断k了.
这种看似要进行复杂的动态处理的问题大多都有规律,这题也不例外.多写两行数据会发现,当n为奇数时,sum(1~n)一定是n的整数倍,即k==0;n为偶数时,k==n/2.
这题赛时就是被吓到了,没找到规律.还是不能慌啊.