Lost

昨天去ND面试 （车上收到有道短信 说下午视频答疑,估计也没什么问题问的就算了 .主考官直接问我什么时候有时间过去 （囧。然后说暑假吧，直接被他否决了 ，说是不能那么晚，现在就得去，平时没时间可以请假一个星期有到三四天就行了...就这样默默地答应了。之后回来打电话给我说明天要过去签协议，补贴方面800保障，出勤好的话每个月加80（可是网上说是1100，这里怎么变了呢 ，他解释什么税收管理费等（= =不是2k以上才要税收吗，显然地有猫腻...被人坑的感觉自然不爽加上路途漫漫（温泉路口 所以今天一大早打电话过去说不去了 酱紫第一次很山寨的笔试面试经历结束了...

        回来继续复习和整理算法。发现模板的《排列与阶乘进制》有猫腻，大牛的代码写的很玄乎看不出是不是真的错了（代码不能多几个注释嘛，然后按自己的想法改动了跑了一下果然假想没错

        现在就说说Coding吧，之前排列与顺序等问题直接都是土土地写地，看了阶乘进制赞叹Knuth大师的伟大（...  然后再看逆过程无比纠结（反正死活看不懂喽，然后偷偷暗想他Coding有问题吧，越看越有问题（= = 鄙视一下自己，经过简单数据验证还好真的是模板的问题（XD

        原先的逆过程：

void back(__int64 perm)
{
	int i, j, k, p[N + 1] = {0},mark[N + 1] = {0};
	i = 1;
	while (perm)
	{
		p[i] = perm % (i + 1);
		perm /= ++i;
	}

	for (i = n-1; i >= 1; --i)
	{
		j = n,k = 0;
		while (k <= p[i])
		{
			if (!mark[j++])
				k++;
		}
		j++;
		a[j] = i + 1;
		mark[j] = 1;
	}
	j = 1;
	while (mark[j])
		j++;
	a[j] = 1;
}
修改后代码：
void back(__int64 perm)
{
	int i, j, k, p[N + 1] = {0},mark[N + 1] = {0};
	i = 1;
	while (perm)
	{
		p[i] = perm % (i + 1);
		perm /= ++i;
	}

	for (i = n-1; i >= 1; --i)
	{
		j = 1,k = 0;
		while (k <= p[i])
		{
			if (!mark[j++])
				k++;
		}
		j--;
		a[n-i] = j;
		mark[j] = 1;
	}
	j = 1;
	while (mark[j])
		j++;
	a[N] = j;
}

顺便贴上转化为阶乘进制代码：
int KnuthPEncode()
{
	int i,j;
	int place = n,e = 0;
	for (i = 1; i <= n; ++i)
	{
		int t = a[i];
		e *= place--;
		for (j = i+1; j <= n ; ++j)
			a[j] < t &&  e++;
	}
	return e;
}