算法概念和板子整理

一些算法概念和板子集中整理

算法概念：

1.错排：

• n个有序的元素应有n!个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排
• d[1] = 0, d[2] = 1,d[3] = 2
• d[n] = (n-1)*(d[n-1]+d[n-2]) 数据一般较大，开long long

2.康托展开：

• 康托展开是一个全排列到一个自然数的映射，从0开始编号，全排列的字符串中某一个的编号是ai*f[len-1-i],ai表示后面小于当前数字的个数，f数组表示阶乘

• 康托逆展开，给定一个自然数，求对应的全排列中的某一个字符串

  • 如果初始序列是12345（第一个），让你求第107个序列是什么。（按字典序递增）

    先把107减1，因为康托展开里的初始序列编号为0
    然后计算下后缀积：
    1 2 3 4 5
    5！ 4！ 3！ 2！1！ 0！
    120 24 6 2 1 1

    106 / 4! = 4 ······ 10 有4个比它小的所以因该是5 从（1，2，3，4，5）里选
    10 / 3! = 1 ······ 4 有1个比它小的所以因该是2 从（1， 2， 3， 4）里选
    4 / 2! = 2 ······ 0 有2个比它小的所以因该是4 从（1， 3， 4）里选
    0 / 1! = 0 ······ 0 有0个比它小的所以因该是1 从（1，3）里选
    0 / 0! = 0 ······ 0 有0个比它小的所以因该是3 从（3）里选

    所以编号107的是 52413

• 代码：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 20;
int f[25];
int num;
vector<char> vec;
void jie_cheng(int n){
	f[0] = f[1] = 1;
	for(int i = 2; i <= n; i++){
		f[i] = i * f[i-1];
	}
	return;
} 
string re_kangtuo(int k){
	int n = vec.size();
	k--;
	string ans = "";
	for(int i = 1; i <= n; i++){
		int t = k / f[n-i];
		ans += vec[t];
		k %= f[n-i];
		vec.erase(vec.begin()+t);
	}
	return ans;
}
signed main()
{
	jie_cheng(N);
	int x = 107;
	for(int i = 1; i <= N; i++){
		if(x / f[i] == 0){
			num = i;
			break;
		}
	}
	for(int i = 1; i <= num; i++){
		vec.push_back('0' + i);
	}
	cout<<re_kangtuo(x)<<endl;
	return 0;
}

3.线性筛：

• O[N]的时间复杂度来求一个范围内的素数。i % prime[j] == 0是关键，举例30=2 * 15 = 10 * 3，为了使得30只筛除一次，当i = 10时，发现i%prime[j] (2) == 0,说明之后的数字也均可以被2整除，所以跳出j的for循环，把筛除的机会留到后面，即用最小的质因子去筛。
• 另外，在这个过程中还可以求一个范围内所有数的最大质因子
• 代码：

void Linear_sieve()
{
	for(int i = 2; i <= n; i++){
		isprime[i] = true;
	}
	for(int i = 2; i <= n; i++){
		if(isprime[i]){
			t++;
			prime[t] = i;
			//p[i] = i;
		}
		for(int j = 1; j <= t&&prime[j]*i<=n; j++){
			//p[prime[j]*i] = max(p[i], prime[j]);
			isprime[prime[j]*i] = false;
			if(i % prime[j] == 0){
				break;
			}
		}
	}
}