#include<cstdio>
int init[10003],tar[10003],T=10000;
void ST(int l,int h)
{
	int t=l;	
	if(l==h) return;
	for(int i=l;i<=h;i+=2)
		tar[t++]=init[i];
	for(int i=l+1;i<=h;i+=2)
		tar[t++]=init[i];
	for(int i=l;i<=h;i++)
		init[i]=tar[i];	
	ST(l,(l+h)/2);
	ST((l+h)/2+1,h);
}
int main()
{	
	for(int i=0;i<T;i++)
		init[i]=i;
	ST(0,T-1);
    printf("%d: ",T);
	for(int i=0;i<T;i++)
		printf("%d ",tar[i]);
	printf("\n");
}
参考了discuss《转载》这篇帖子。
生成序列后用n*n暴力了一下，还比较快，用了0.28s，看来常数影响很大啊