3257842_ce.cpp

部分PKU上的源码

#include <iostream>
#include<string>
using namespace std;
long long  num[21][21][2];long long work[21][21][2],out[21];
long long i,j,k,count,t,numoutput;
long long K,N,C;
void display(long long number);
long long get (long long x,long long y,long long z);
void output(long long x,long long number);
void output2(long long x,long long number,long long z,long long chu);

	long long main ()
{cin>>K;
memset(num,0,21*21*2);
 memset(work,0,21*21*2);
num[2][1][0]=0;num[2][1][1]=1;	num[2][2][0]=1;num[2][2][1]=0;
for(i=3;i<=20;i++)
  for(j=1;j<=i;j++)
  {get(i,j,1);get(i,j,0);}
for(i=0;i<K;i++)
{for(j=1;j<=20;j++) out[j]=j;
numoutput=1;
	cin>>N>>C; 
output(N,C);
cout<<endl;
}
	return 0;
}
	long long get (long long x,long long y,long long z)
{if(work[x][y][z]==1) return num[x][y][z];
else{if(z==0) {for(i=1;i<y;i++) num[x][y][z]+=get(x-1,i,1);}
	   else {for(i=y;i<=x-1;i++) num[x][y][z]+=get(x-1,i,0);}
	    work[x][y][z]=1;
		return num[x][y][z];}
}

void output(long long x,long long number)
{if(x==2){if(number==2) display(2),display(1);
           else display(1),display(1);
            }
	else{count=0;
	for(i=1;i<=x;i++)
	{count+=num[x][i][0]; if(count>=number) {count-=num[x][i][0];display(i);output2(x-1,number-count,1,i);return;}
	count+=num[x][i][1]; if(count>=number) {count-=num[x][i][1];display(i);output2(x-1,number-count,0,i);return;}
	}
}
}
void output2(long long x,long long number,long long z,long long chu)
{if(x==2){if(z==0) display(2),display(1);
           else display(1),display(1);
            }
else{count=0;
	if(z==1) {
	for(i=1;i<=x;i++) 
	{
		count+=num[x][i][1]; 
		if(count>=number) {count-=num[x][i][1];display(i);output2(x-1,number-count,0,i);return;}
	}
}
else {
	for(i=chu;i<=x;i++) 
	{
		count+=num[x][i][0]; 
		if(count>=number) {count-=num[x][i][0];display(i);output2(x-1,number-count,1,i);return;}
	}
}
}
}
	
	
	void display(long long number)
{t=0;
	for(k=1;k<=20;k++) 
	{if(out[k]!=0) t++;
	if(t==number) {
		if(numoutput==1) cout<<k,numoutput++;
		else cout<<" "<<k;
	    out[k]=0,k=20;
	}
	}
}