自动搬运

查看原文

来自洛谷，原作者为

	Falashiro 丝之歌什么时候出

搬运于2025-08-24 22:29:21，当前版本为作者最后更新于2021-02-08 13:21:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\sum\limits_{i=1}^{n}i=\frac{n\times(n+1)}{2}$，$\sum\limits_{i=2}^{n+1}i=\frac{n\times(n+3)}{2}$，

若 $m\ge\frac{n\times(n+3)}{2}$，可以给出构造解：

$2,3,\dots,n-1,n,m-\frac{(n-1)\times(n+2)}{2}$，无法表示出 $m-1$。

若 $m<\frac{n\times(n+1)}{2}$，无法分为 $n$ 个不相同的正整数，显然无解。

若 $\frac{n\times(n+1)}{2}\le m<\frac{n\times(n+3)}{2}$，

假设有解，不妨认为构造出来的序列 $a$ 单调递增，
设 $m=\frac{n\times(n+1)}{2}+t$，那么所有由 $n$ 个不相同的正整数组成且和为 $m$ 的单调递增的序列均可以这么得到：有一个初始为 $1,2,\dots,n-1,n$ 的序列，每次给一个数加 $1$，加 $t$ 次，中途需要保持序列单调递增，这相当于进行若干次后缀加，总的增量为 $t$。

结论：

若 $n\ge4$，对于得到的任意一个序列 $a$，和任意一个 $2\le i\le n$，都有 $(\sum\limits_{j=1}^{i-1}a_j)+1\ge a_i$。

证明：

$t<\frac{n\times(n+3)}{2}-\frac{n\times(n+1)}{2}$，即 $t<n$，

如果要使上述结论不成立，设要使得它在 $i$ 的位置不成立，显然一直给 $a_i$ 加 $1$ 是最优的，给 $a_i$ 加 $1$ 的需要进行 $n-i+1$ 次加法，$a_i$ 最多能被加 $\lfloor\frac{t}{n-i+1}\rfloor\le \lfloor\frac{n-1}{n-i+1}\rfloor$ 次，

现在需要证明 $a_i>(\sum\limits_{j=1}^{i-1}a_j)+1$ 是不可能的，

即证明 $i+\lfloor\frac{n-1}{n-i+1}\rfloor\le \frac{i\times(i-1)}{2}+1$，

假设现在 $i$ 已经固定，则 $n=i$ 时，$\lfloor\frac{n-1}{n-i+1}\rfloor$ 最大，它的值为 $i-1$，

现在需要证明 $i+i-1\le\frac{i\times(i-1)}{2}+1$，

即 $4i-4\le i^2-i$，

在 $i\ge4$ 时，即 $n\ge4$ 时，上式成立，证毕。

接下来可以利用这个结论完成本题证明：

若 $n<4$，暴力枚举可得无解，若 $n\ge4$：

因为 $t<n$，后缀加无法对 $a_1$ 造成影响，所以 $a_1=1$，第一个数可以表示出区间 $[1,1]$ 内的所有正整数，假设目前已经得到了 $a_1$ 至 $a_x$ 可以表示区间 $[1,s]$ 内的所有正整数且 $s=\sum\limits_{i=1}^xa_i$，则加入 $a_{x+1}$ 后一定可以表示区间 $[a_{x+1},a_{x+1}+s]$ 内的所有正整数，由之前的结论可得：$s+1\ge a_{x+1}$，那么 $[1,s]\cup[a_{x+1},a_{x+1}+s]=[1,a_{x+1}+s]$，当前的区间右端点仍为已加入的所有数的和，最后将 $a_n$ 加入后，一定可以表示区间 $[1,\sum\limits_{i=1}^na_i]$ 内所有正整数，即可以表示出区间 $[1,m]$ 内所有正整数。

所以当 $\frac{n\times(n+1)}{2}\le m<\frac{n\times(n+3)}{2}$ 时，无解。

code：

#include<bits/stdc++.h>
using namespace std;
int read(){
	int w=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')w=w*10+c-48,c=getchar();
	return w;
}
int T,n,m;
signed main(){
	T=read();
	while(T--){
		n=read(),m=read();
		if(n*(n+3)/2>m){
			puts("-1");
			continue;
		}
		for(int i=2;i<=n;i++)
			printf("%d ",i);
		printf("%d\n%d\n",m-(n-1)*(n+2)/2,m-1);
	}
	return 0;
}