https://www.luogu.org/problemnew/show/P1118
next_permutation的第二个参数是最后一个元素的下一个元素，sort也是一样！有毒！这么低级的错误。而且应该是用do_while因为原始排列也要考虑！
使用sort跳过一些permutation的原理来源于：
1.假设解存在，那么对称位置的两个元素交换也是一种解
2.我们要求第一种解，必定是左边元素小于右边对应元素的
3.当某个排列导致当前大于sum，怎么证明发现该元素之后的任意排列都是大于sum的呢？
4.假如发现该元素的位置在中间的右侧，那么把更大的元素前移只会让答案变大
5.假如发现该元素的位置在中间的左侧，若这其中有解，必定在之前已经搜索过对应位置的了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
/*
int N,sum; int cntn[13]; int solve(vector<int> &cur,vector<int> &next,int nf){
next.clear();
next.push_back(nf); int pre=nf;
int sz=cur.size();
for(int i=0;i<sz;i++){
int tmp=cur[i]-pre;
if(tmp<=0)
return 0;
next.push_back(tmp);
pre=tmp;
}
return 1;
} void dfs(int n,vector<int> cur){
if(n==N){
//wrong, maybe N+1
int sz=cur.size();
memset(cntn,0,sizeof(cntn)); for(int i=0;i<sz;i++){
if(cur[i]>n||cntn[cur[i]])
return;
else{
cntn[cur[i]]++;
}
} for(int i=0;i<sz;i++){
printf("%d%c",cur[i]," \n"[i==sz-1]);
}
exit(0);
}
else{
vector<int> next;
for(int nextfirst=1;nextfirst<=cur[0]-1;nextfirst++){
int suc=solve(cur,next,nextfirst);
if(suc){
dfs(n+1,next);
}
else{
;
}
}
}
} int main(){
scanf("%d%d",&N,&sum);
vector<int> v;
v.push_back(sum);
dfs(1,v);
} */
int N,sum; int ans[][];
int pas[][]; inline int findsum(){
/*for(int i=2;i<=N;i++){
for(int j=1;j<=N+1-i;j++){
ans[i][j]=ans[i-1][j]+ans[i-1][j+1];
if(ans[i][j]>sum)
return -1;
}
}*/
int tmp=;
for(int i=;i<=N;i++){
//printf("%d ",pas[N][i]);
tmp+=pas[N][i]*ans[][i];
if(tmp>sum){
sort(&ans[][i],&ans[][N]+,greater<int>());
//因为nextpermutation绝对会把大的数字前移，
//根据对称性我们会优先得到小的解，也就是这个不会过半
//所以下一次nextpermutation绝对是会变大的
return -;
}
}
//printf("\n");
//cout<<"tmp="<<tmp<<endl;
return tmp;
} int main(){
scanf("%d%d",&N,&sum); /*if(N<=2){
if(N==1){
if(sum==1){
printf("1\n");
}
}
else{
if(sum==3){
printf("1 2\n");
}
}
return 0;
}*/ for(int i=;i<=N;i++){
ans[][i]=i;
} pas[][]=;
//printf("1\n");
for(int i=;i<=N;i++){
pas[i][]=pas[i][i]=;
for(int j=;j<=i-;j++)
pas[i][j]=pas[i-][j]+pas[i-][j-];
/*for(int j=1;j<=i;j++){
printf("%d ",pas[i][j]);
}
printf("\n");*/
} /*for(int i=1;i<=N;i++){
printf("%d ",pas[N][i]);
}
printf("\n");*/ do{
if(sum==findsum()){
for(int i=;i<N;i++){
printf("%d%c",ans[][i+]," \n"[i==N-]);
}
break;
}
else{
/*for(int i=0;i<N;i++){
printf("%d%c",ans[1][i+1]," \n"[i==N-1]);
}*/
}
}while(next_permutation(&ans[][],&ans[][N]+));
}