思博算法复习笔记

lyc 一直在写 CF 题
lyc 发现他不会写 OI 题了
lyc 发现他啥算法都不会
lyc 来复习思博算法了

矩阵快速幂

大概的讲解

设 $A$ 是 $n*m$ 矩阵，$B$ 是 $m*p$ 矩阵， $A\times B = C$，则 $C$ 是 $n*p$ 矩阵，有

$C_{i,j}=\sum\limits_{k=1}^m A_{i,k} \times B_{k,j}$

设 $1*n$ 矩阵 $F$，$n*n$ 矩阵 $A$，$F^{'} = F \times A$。称 $A$ 为转移矩阵。理解为 $F$ 中的第 $k$ 个值以 $A_{k,j}$ 的系数累加到 $F^{'}$ 的第 $j$ 个值上。

矩阵乘法满足结合律，故可以使用快速幂加速。

板子

const int MAX_Mat=5;
struct Matrix{
	int r=2,c=2;
	int m[MAX_Mat][MAX_Mat];
	Matrix(int x,int y){
		r=x;c=y;
		memset(m,0,sizeof(m));
	}

	Matrix operator*(const Matrix &b) const{
		Matrix ans(r,b.c);
		for (int i=1;i<=r;i++)
			for (int j=1;j<=b.c;j++)
				for (int k=1;k<=c;k++)
					ans.m[i][j]=ans.m[i][j]+m[i][k]*b.m[k][j];
		return ans;
	}
};

Matrix base(3,3),ans(1,3);

void init(){
	memset(ans.m,0,sizeof(ans.m));
	memset(base.m,0,sizeof(base.m));
}

void ksm(int y){
	while (y>0){
		if (y%2==0){
			y/=2;
			base=base*base;
		}
		ans=ans*base;
		y--;
	}
}

习题

• P1939 【模板】矩阵加速（数列）
  板子题（
• CF1117D Magic Gems
  首先推出来一个显然的 dp，然后发现显然可以矩阵加速（

01Trie

没啥好说的（

板子

const int MAXM=10000005;
struct trie{
	int nex[MAXM][3];
	int exist[MAXM];
	int Index=0;

	trie(){
		memset(nex,0,sizeof(nex));
	}

	void insert(int s){
		int p=0;
		for (int i=30;i>=0;i--){
			int now=(s>>i)&1;
			if (!nex[p][now]) nex[p][now]=++Index;
			p=nex[p][now];
		}
	}

	int query(int s){
		int ans=0;
		int p=0;
		for (int i=30;i>=0;i--){
			int now=(s>>i)&1;
			if (nex[p][now^1]){
				p=nex[p][now^1];
				ans+=1<<i;
			}
			else p=nex[p][now];
		}
		return ans;
	}
};

习题

• Loj #10050 The XOR Largest Pair
  板子题（
• Loj #10051 Nikitosh 和异或
  先做一个前缀异或和
  处理出 $l_i$ 表示在 $1-i$ 中任取两个不相同的数的异或最大值和类似的 $r_i$
  之后统计答案
• P4551 最长异或路
  对于每个点处理出树上前缀和 然后直接做

Hash