学习小结 - 洛谷保存站

# **数论**

### **①**素数&素数筛法：
筛法有欧拉筛与埃氏筛两种，在时间复杂度上前者更优

代码：

欧拉筛(线性筛)
```cpp
void gp(ll r){
	cnt=0;
	ll i,j;
	for(i=2;i<=r;i++){
		c[i]=c[i-1];
		a[i]=a[i-1];
		if(!p[i]){
			z[++cnt]=i;
			c[i]++;
			a[i]+=i;
		} 
		for(j=1;j<=cnt && i*z[j]<=r;j++){
			p[i*z[j]]=true;
			if(i%z[j]==0) break;
		}
	}
}
//时间O(n)
```

埃氏筛

```cpp
void ee(int x){
	for(int i=2;i<=x;i++){
		p[i]=true;
	}
	p[0]=p[1]=false;	
	for(int i=2;i*i<=x;i++){
		if(p[i]){
			for(int j=i*i;j<=x;j+=i){
				p[j]=false;
			}
		}
	}
}
//时间O(n logn)
```

判断素数就是从2到根号n（i*i<=n）

素数分解同判断看能否会被2到根号n的数整除（x|n）

### **整数唯一分解定理**

N=p1^r1*p2^r2*...*pk^rk

法一：通过素数分解的暴力枚举的方法找

法二：素数打表，用筛法将范围内的素数全部求出来一个个判断能否整除

进阶例题. NKOJ P7462

# **同余**

引子：

How long do you need to work out this problem?

123456789*987654321=()

A.1.....6

B.1.....7

C.1.....8

D.1.....9

根据自己给的答案得到的亿点提示肯定选D。这是因为选项结果的各位不同从而导致的简便。

任意数都可以表示为X=a*b+r

所以我们有了一个新运算符%（mod）表示取余。则有下面的公式：

(a+b)%m=((a%m)+(b%m))%m

(a-b)%m=((a%m)+(b%m)+m)%m

(a\*b)%m=((a%m)*(b%m))%m

注意的是减法中的“+m”是因为a mod m可能小于b mod m。

乘法中相乘看范围会不会  _~~bao~~_  int

除法是坚决不允许的（只能用逆元）

幂的取模避免爆炸要用快速幂并且快速幂中看要不要用快慢乘法

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll mod_pow(ll x,ll n,ll mod){//快速幂 
	ll ans=1;
	while(n>0){
		if(n&1) ans=ans*x%mod;//乘法可能爆炸 
		x=x*x%mod;//again 
		n>>=1;
	}
	return ans;
}
ll slow_mul(ll a,ll b,ll mod){//慢速乘法 
	ll ans=0;
	while(b){
		if(b&1) ans=(ans+a)%mod;
		a=(a+a)%mod;
		b>>=1;
	}
	return ans;
}
ll quick_mul(ll a,ll b,ll mod){//快速乘法 
	ll ans=0;
	while(b){
		if(b&1) ans=(ans+a)%mod;
		b=b>>1;
		a=(a<<1)%mod;
	}
	return ans;
}

int main(){
	long long x,n,mod;
	cin>>x>>n>>mod;
	cout<<quick_mul(x,n,mod);
	return 0;
}
```

### **正题**

同余的概念：a%m=b%m

记做：a≡b(mod m)

#### 定理&性质
- 如a≡b(mod m)且c≡d(mod m)则:

a+c≡b+d(mod m)

a-c≡b-d(mod m)

a\*c≡b\*d(mod m)

- bushuole

## **我们终于学到了树形结构了TAT**，~~太不容易啦~~

### **分为两个板块**

① _**树状数组**_

② _**线段树**_

# 一：树状数组

### 1. 树状数组的用途及特点：

1. 利用数的二进制特征进行检索的一种树状结构，它能够高效地获取数组中连续k个数的和。
2. 通常用于“数组A中的元素可能不断地被修改，怎样快速地获取区间和？
”
3. 高效且极其简洁

4. 图示：
  
![logo](https://cdn.luogu.com.cn/upload/image_hosting/e38qk50l.png?x-oss-process=image/resize,m_lfit,h_170,w_225)

### 2. 操作方式：

#### 1. lowbit
- [ ] 原理：

![logo](https://cdn.luogu.com.cn/upload/image_hosting/8dnefswt.png?x-oss-process=image/resize,m_lfit,h_170,w_225)

- [ ] 功能：找到x的二进制数的最后一个1

- [ ] 代码
```cpp
int lowbit(int x){
	return x&(-x);
}
```

#### 2. getsum

- [ ] 思路：当我们求A[1]+...+A[x]的之和时,
C[x]如果包含的不一定是1..x的全部和,(比如C[6]=A[5]+A[6])
就需要再找一个C\[k\](显然k<x)累加起来,这个k我们称之为x的前驱，例如:
A[1]+A[2]+..+A[6]=C[6]+C[4]
A[1]+A[2]+..+A[7]=C[7]+C[6]+C[4]

前驱的编号：比自己小的,最近的,最末连续0比自己多的数
所以x的前驱k=x-lowbit(x)   //相当于x剪掉了自己最右边的1

- [ ] 代码
```cpp
int getsum(int x)     //求A[1]+A[2]+...+A[x]
{
	int sum= 0;
	for ( int k = x; k >= 1; k -= lowbit(k) )  sum += c[k];
	return sum;
}

```

- [ ] 拓展：这样只能求得前缀和，万一是区间和怎么办？别急getsum(y)-getsum(x-1)

#### 3.add(修改操作)

- [ ] 思路：修改了某个A[i],就需改动所有包含A[i]的C[j];
从上图看就是要更改从改叶子节点到根节点路径上的所有C[j]
修改了某个A[i],就需改动所有包含A[i]的C[j];
从上图看就是要更改从改叶子节点到根节点路径上的所有C[j]

怎么求一个节点的父节点嘞?

so eazy!

规律:父节点：比自己大的,最近的,末位连续0比自己多的数
x节点父亲的编号 = x+lowbit(x)

- [ ] 代码

- [ ] 
```cpp
void add(int x,int k){
	for(int i=x;i<=n;i+=lowbit(i)){
		c[i+=k;
	}
}
```

#### 4.例题（只想写一道，还要写线段树）
  见   [某考试列表](http://oi.nks.edu.cn:19360/zh/Contest/Details/3125)

经典例题[ 传送门](https://www.luogu.com.cn/problem/P1908)

这道题是模板的树状数组加离散化，离散化中先去重，再二分出此数的位置（下标），用下标去代替此数值，就能AC了。代码

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,ans=0;
int a[500010],b[500010],c[500010];
int lowbit(int x){
	return x&(-x);
}
int getsum(int x){
	int sum=0;
	for( int i=x;i>0;i-=lowbit(i)) sum+=c[i];
	return sum;
}
void modify(int x,int d){
	for(int i=x;i<=n;i+=lowbit(i)) c[i]+=d;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	int m=unique(b+1,b+n+1)-b-1;//离散化
	for(int i=n;i;i--){
		int k=lower_bound(b+1,b+m+1,a[i])-b;
		ans+=getsum(k-1);
		modify(k,1);
	}
	cout<<ans;
	return 0;
}
```

TAT,难题找不到

# 二:线段树

_**~~这个就复杂得多是树状数组的Pro  Max，但是能维护的值也很多~~**_ 
### 1. 线段树的用途及特点：

1. 定义：线段树是一种特殊的二叉树，它可以将一个线性的序列组织成一个树状结构，从而可以在对数的时间复杂度下访问序列上的任意一个区间并进行维护。

2. 要么没有子节点，要么有2个子节点
长度为n的序列建的线段树，节点个数为:(2n-1)
长度为n的序列建的线段树，树深度为:logn

3. 注意：线段树所维护的信息必须具有可合并性：如求和sum、最值等，但众数不可合并
一个结点上可以维护多种信息，将若干个结点的信息合并，就能得到任意区间的信息。
例如，在上图中，如果希望获得区间[x,y]的信息，只需要将结点[x,z]和结点[z,y]的信息合并即可。

### 2. 操作方式：

#### 1. 定义线段树组：

```cpp
struct node{
	int l,r;//区间[l,r] 
	int val;//维护的值 
	int lazy; 
}tree[4*N];
```

#### 2. pushuup:
 
```cpp
void pushup(int p){//val是区间和,合并区间和 
	tree[p].val=tree[2*p].val+tree[2*p+1].val;
}
```
#### 3. maketree:
```cpp
void maketree(int p,int x,int y){//节点编号p,区间[x,y] 
	tree[p].l=x;
	tree[p].r=y;
	if(x==y){//叶子节点
		tree[p].val=a[x];
		//有些题它没有a序列，要因题而定，要么赋为0，要么赋为极值
		return ; 
	}
	int mid=(x+y)/2;
	maketree(p<<1,x,mid);//左子树构造，同p*2,位运算更快 
	maketree(p<<1|1,mid+1,y);//右子树构造，同p*2+1
	pushup(p);//回溯时，更新区间和 
}

```

#### 4. 单点修改：
```cpp
void ADD(int p,int k,int d){//a[k]+d，当前处理到p号节点 
	if(tree[p].l==tree[p].r){
		tree[p].val+=d;
		return ;
	}
	if(k<=tree[p<<1].r) ADD(p<<1,k,d);
	if(k>=tree[p<<1|1].l) ADD(p<<1|1,k,d);
	pushup(p);//回溯时，更新区间和 
}
```

#### 5. 区间修改（就是单点修改上多加了个lazy，如果此点的区间包含需要改的数，就存在lazy这里。还要加两个函数maketag和pushdown）：
```cpp
void maketag(int p,int len,int x){
	tree[p].lazy+=x;//修改当前点的延迟标记 
	tree[p].val+=len*x;//修改区间和 
}
void pushdown(int p){//此函数是为了求区间和所增设
	int M=tree[p].r+tree[p].l>>1;//下放，将累计在点k上的lazy值下放到他的儿子节点 
	maketag(p<<1,M-tree[p].l+1,tree[p].lazy);
	maketag(p<<1|1,tree[p].r-M,tree[p].lazy);
	tree[p].lazy=0;//已传到下一层，避免重复，清空标记 
}
void add(int p,int x,int y,int k){//[x,y]区间加上k 
	if(tree[p].l>y||tree[p].r<x) return ;//不相交 
	if(x<=tree[p].l&&tree[p].r<=y){//完全包含 
		int len=tree[p].r-tree[p].l+1;
		maketag(p,len,k);
		return ;
	}
	if(tree[p].lazy) pushdown(p);//遇到延迟标记，传递给儿子 
	add(p<<1,x,y,k);//左儿子相交 
	add(p<<1|1,x,y,k);//右儿子相交 
	pushup(p);//更新 
}
```

#### 6. getsum（单点查询）：
```cpp
int getsum(int p,int s,int t){//查询[s,t]的区间和，当前查到P节点 
	if(t<tree[p].l||s>tree[p].r) return 0;//区间完全 不相交 
	if(s<=tree[p].l&&tree[p].r<=t) return tree[p].val;//查询区间完全包含P节点的区间 
	return getsum(p<<1,s,t)+getsum(p<<1|1,s,t);//其余情况，左右各一段，需要继续递归 
}
```

#### 7. getsum（区间查询的）
```cpp
int getsum(int p,int x,int y){
	if(tree[p].l>y||tree[p].r<x) return 0;//不相交 
	if(x<=tree[p].l&&tree[p].r<=y){//全包含，直接返回 
		return tree[p].val;
	}
	if(tree[p].lazy) pushdown(p);//下放 
	return getsum(p<<1,x,y)+getsum(p<<1|1,x,y); 
}
```

#### 8. 有些题要查询单点的值，可用getsum(1,x,x);

## 注：某些题数据过于
# 大

## 所以，需要使用动态开点

此方法，删去了maketree这个函数，而将l,r（这个点的）区间，附带在每个函数当中 （后有例题，以助理解）

### 3. 经典例题

[某题目列表](http://oi.nks.edu.cn:19360/zh/Contest/RankListOI/3125)

---

[经典例题1](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3125&tid=X)

这道题就是纯纯的单点修改+区间查询模版题，把区间查询的getsum和pushup中的求和操作改为求最大值max，就可以把分数变绿了，代码：

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=100000+10;
int n,a[N],m;
struct node{
	int l,r;//区间[l,r] 
	int val;//维护的值 
}tree[4*N];
void pushup(int p){//val是区间和,合并区间和 
	tree[p].val=max(tree[2*p].val,tree[2*p+1].val);
}
void maketree(int p,int x,int y){//节点编号p,区间[x,y] 
	tree[p].l=x;
	tree[p].r=y;
	if(x==y){//叶子节点
		tree[p].val=a[x];
		return ; 
	}
	int mid=(x+y)/2;
	maketree(p<<1,x,mid);//左子树构造，同p*2,位运算更快 
	maketree(p<<1|1,mid+1,y);//右子树构造，同p*2+1
	pushup(p);//回溯时，更新区间和 
}
void ADD(int p,int k,int d){//a[k]+d，当前处理到p号节点 
	if(tree[p].l==tree[p].r){
		tree[p].val+=d;
		return ;
	}
	if(k<=tree[p<<1].r) ADD(p<<1,k,d);
	if(k>=tree[p<<1|1].l) ADD(p<<1|1,k,d);
	pushup(p);//回溯时，更新区间和 
}
int getval(int p,int k){//查询a[k]的值，当前查到P节点 
	if(tree[p].l==tree[p].r) return tree[p].val;
	if(k<=tree[p<<1].r) return getval(p<<1,k);
	if(k>=tree[p<<1|1].l) return getval(p<<1|1,k);
}
int getsum(int p,int s,int t){//查询[s,t]的区间和，当前查到P节点 
	if(t<tree[p].l||s>tree[p].r) return -1e18;//区间完全 不相交 
	if(s<=tree[p].l&&tree[p].r<=t) return tree[p].val;//查询区间完全包含P节点的区间 
	return max(getsum(p<<1,s,t),getsum(p<<1|1,s,t));//其余情况，左右各一段，需要继续递归 
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	maketree(1,1,n);
	for(int i=1;i<=m;i++){
		int s;
		int x,y; 
		cin>>s>>x>>y;
		if(s==1){
			ADD(1,x,y);
		}
		else{
			cout<<getsum(1,x,y)<<'\n';
		}
	} 
	return 0;
} 
```

---

[经典例题2](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3125&tid=a)

这道题就是纯纯的区间修改+区间查询模版题，把区间查询的getsum和pushup中的求和操作改为求最大值max，就可以把分数变绿了，还有maktag中val赋值变成x不是len*x（因为这是求最大值，而不是区间和），pusdown中的lazy下放，要赋值为0，代码：

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=100000+10;
int n,a[N],m;
struct node{
	int l,r;//区间[l,r] 
	int val;//维护的值 
	int lazy; 
}tree[4*N];
void pushup(int p){//val是区间和,合并区间和 
	tree[p].val=max(tree[2*p].val,tree[2*p+1].val);
}
void maketree(int p,int x,int y){//节点编号p,区间[x,y] 
	tree[p].l=x;
	tree[p].r=y;
	if(x==y){//叶子节点
		tree[p].val=a[x];
		return ; 
	}
	int mid=(x+y)/2;
	maketree(p<<1,x,mid);//左子树构造，同p*2,位运算更快 
	maketree(p<<1|1,mid+1,y);//右子树构造，同p*2+1
	pushup(p);//回溯时，更新区间和 
}
void maketag(int p,int len,int x){
	tree[p].lazy+=x;//修改当前点的延迟标记 
	tree[p].val+=x;//修改区间和 
}
void pushdown(int p){
	int M=tree[p].r+tree[p].l>>1;//下放，将累计在点k上的lazy值下放到他的儿子节点 
	maketag(p<<1,M-tree[p].l+1,tree[p].lazy);
	maketag(p<<1|1,tree[p].r-M,tree[p].lazy);
	tree[p].lazy=0;//已传到下一层，避免重复，清空标记 
}
void add(int p,int x,int y,int k){//[x,y]区间加上k 
	if(tree[p].l>y||tree[p].r<x) return ;//不相交 
	if(x<=tree[p].l&&tree[p].r<=y){//完全包含 
		int len=tree[p].r-tree[p].l+1;
		maketag(p,len,k);
		return ;
	}
	if(tree[p].lazy) pushdown(p);//遇到延迟标记，传递给儿子 
	add(p<<1,x,y,k);//左儿子相交 
	add(p<<1|1,x,y,k);//右儿子相交 
	pushup(p);//更新 
}
int getsum(int p,int x,int y){
	if(tree[p].l>y||tree[p].r<x) return 0;//不相交 
	if(x<=tree[p].l&&tree[p].r<=y){//全包含，直接返回 
		return tree[p].val;
	}
	if(tree[p].lazy) pushdown(p);//下放 
	return max(getsum(p<<1,x,y),getsum(p<<1|1,x,y)); 
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	maketree(1,1,n);
	cin>>m;
	for(int i=1;i<=m;i++){
		string s;
		int x,y,z; 
		cin>>s>>x>>y;
		if(s=="ADD"){
			cin>>z;
			add(1,x,y,z);
		}
		else{
			cout<<getsum(1,x,y)<<'\n';
		}
	} 
	return 0;
} 
```

---

[经典难题](https://www.luogu.com.cn/problem/P1253)

此题虽为绿题，但是把分数变绿也只有**~~亿点点难~~**；

把模板分两个来写，一个用来加，一个用来变。在加上动态开点，就能AC!——十分简单吧！（花了我一节晚自习）

代码：
```cpp
#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int N=1000010;
int n,q,a[N];
//具体说一下这个动态开点：
//动态开点顾名思义，就是需要这个点才定义它
//比传统的maketree而言
//直接省下很多的空间

//动态开点舍去了maketree
//而将此点的范围自带于函数之中
//如果没有这个点，那么就现场就“生”一个
//就解决了节点冗多的情况
struct node{
	int l,r;//区间[l,r] 
	int val;//维护的值 
	int lazy; 
	int lazy_ne;
}tree[4*N];
void pushup(int p){//val是区间和,合并区间和 
	tree[p].val=max(tree[p<<1].val,tree[p<<1|1].val);
}
void maketree(int p,int x,int y){//节点编号p,区间[x,y] 
	tree[p].l=x;
	tree[p].r=y;
	tree[p].lazy=0;
	tree[p].lazy_ne=-1e18;
	if(x==y){//叶子节点
		tree[p].val=a[x];
		return ; 
	}
	int mid=(x+y)/2;
	maketree(p<<1,x,mid);//左子树构造，同p*2,位运算更快 
	maketree(p<<1|1,mid+1,y);//右子树构造，同p*2+1
	pushup(p);//回溯时，更新区间和 
}
void maketag(int p,int x){
	tree[p].lazy+=x;//修改当前点的延迟标记 
	tree[p].val+=x;//修改区间和 
}
void maketag1(int p,int x){
	tree[p].lazy_ne=x;//修改当前点的延迟标记 
	tree[p].lazy=0;
	tree[p].val=x;//修改区间和 
}
void pushdown(int p){
	maketag(p<<1,tree[p].lazy);
	maketag(p<<1|1,tree[p].lazy);
	tree[p].lazy=0;//已传到下一层，避免重复，清空标记 
}
void pushdown1(int p){
	maketag1(p<<1,tree[p].lazy+tree[p].lazy_ne);
	maketag1(p<<1|1,tree[p].lazy+tree[p].lazy_ne);
	tree[p].lazy=0;
	tree[p].lazy_ne=-1e18;//已传到下一层，避免重复，清空标记 
}
void add(int p,int x,int y,int k){//[x,y]区间加上k 
	if(tree[p].l>y||tree[p].r<x) return ;//不相交 
	if(x<=tree[p].l&&tree[p].r<=y){//完全包含 
		maketag(p,k);
//		cout<<"add:"<<" p:"<<p<<" l:"<<tree[p].l<<" r:"<<tree[p].r<<" val:"<<tree[p].val<<" lazy:"<<tree[p].lazy<<'\n';
		return ;
	}
	if(tree[p].lazy_ne!=-1e18) pushdown1(p);//遇到延迟标记，传递给儿子 
	if(tree[p].lazy) pushdown(p);//遇到延迟标记，传递给儿子 
	add(p<<1,x,y,k);//左儿子相交 
	add(p<<1|1,x,y,k);//右儿子相交 
	pushup(p);//更新 
//	cout<<"add:"<<" p:"<<p<<" l:"<<tree[p].l<<" r:"<<tree[p].r<<" val:"<<tree[p].val<<" lazy:"<<tree[p].lazy<<'\n';
}
void add1(int p,int x,int y,int k){//[x,y]区间变为k 
	if(tree[p].l>y||tree[p].r<x) return ;//不相交 	
	if(x<=tree[p].l&&tree[p].r<=y){//完全包含 
		maketag1(p,k);
//		cout<<"add1:"<<" p:"<<p<<" l:"<<tree[p].l<<" r:"<<tree[p].r<<" val:"<<tree[p].val<<" lazy:"<<tree[p].lazy_ne<<'\n';
		return ;
	}
	if(tree[p].lazy_ne!=-1e18) pushdown1(p);//遇到延迟标记，传递给儿子 
	if(tree[p].lazy) pushdown(p);//遇到延迟标记，传递给儿子 
	add1(p<<1,x,y,k);//左儿子相交 
	add1(p<<1|1,x,y,k);//右儿子相交 
	pushup(p);//更新 
//	cout<<"add1:"<<" p:"<<p<<" l:"<<tree[p].l<<" r:"<<tree[p].r<<" val:"<<tree[p].val<<" lazy:"<<tree[p].lazy_ne<<'\n';
}
int getsum(int p,int x,int y){
	if(tree[p].l>y||tree[p].r<x) return -1e18;
//	cout<<"getsum:"<<" p:"<<p<<" l:"<<tree[p].l<<" r:"<<tree[p].r<<" val:"<<tree[p].val<<" lazy:"<<tree[p].lazy<<'\n';
	if(x<=tree[p].l&&tree[p].r<=y){
		return tree[p].val;
	}
	if(tree[p].lazy_ne!=-1e18) pushdown1(p);
	if(tree[p].lazy) pushdown(p);
	return max(getsum(p<<1,x,y),getsum(p<<1|1,x,y));
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	maketree(1,1,n);
	for(int i=1;i<=q;i++){
		int op;
		cin>>op;
		int l,r,x;
		cin>>l>>r;
		if(op==3){
			cout<<getsum(1,l,r)<<'\n';
		}
		else{
			cin>>x;
			if(op==1){
				add1(1,l,r,x);
			}
			else if(op==2){
				add(1,l,r,x);
			}
		}
	} 
	return 0;
}
```

# 状压DP

## 一、基本概念
状压DP（状态压缩动态规划）是一种特殊的动态规划方法，主要用于处理状态包含多个布尔属性（通常是"选/不选"或"存在/不存在"）的问题。它通过将状态压缩为一个整数（通常是二进制数）来减少状态空间，提高算法效率。

### 二、适用场景
问题的状态可以表示为一系列二元选择（是/否）

状态维度较高但每个维度只有少量可能值

常规DP方法会导致状态空间爆炸

典型问题：

旅行商问题（TSP）

棋盘覆盖问题

任务分配问题

子集选择问题

### 三、核心思想
状态压缩：用一个整数的二进制位表示各个元素的状态

例如：1011表示第0、1、3个元素被选中，第2个未被选中

状态转移：基于当前状态和决策，计算可能的新状态

记忆化：存储已计算的状态结果，避免重复计算

### 四、实现技巧
#### 1. 位运算基础

```cpp
// 常用位运算操作
S & (1 << i)    // 检查第i位是否为1
S |= (1 << i)   // 将第i位设为1
S &= ~(1 << i)  // 将第i位设为0
S ^= (1 << i)   // 翻转第i位
S = S & (S - 1) // 将最低位的1设为0
```

#### 2. 状态表示
通常用dp[mask][...]表示状态，其中：

mask是状态压缩的整数

可能有其他维度表示附加信息（如当前位置、已选数量等）

#### 3. 常见模式

```cpp
// 初始化
dp[0][...] = base_case;

// 状态转移
for (int mask = 0; mask < (1 << n); ++mask) {
    for (int i = 0; i < n; ++i) {
        if (!(mask & (1 << i))) {  // 如果第i位未被选中
            int new_mask = mask | (1 << i);
            dp[new_mask][...] = update(dp[mask][...], ...);
        }
    }
}

// 结果通常在dp[(1 << n) - 1][...]
```

### 五、经典例题
#### 1. 旅行商问题（TSP）

```cpp
int dp[1 << n][n]; // dp[mask][u]表示经过mask中的城市，最后在u城市的最小花费

memset(dp, INF, sizeof(dp));
dp[1][0] = 0; // 从城市0出发

for (int mask = 1; mask < (1 << n); ++mask) {
    for (int u = 0; u < n; ++u) {
        if (!(mask & (1 << u))) continue;
        for (int v = 0; v < n; ++v) {
            if (mask & (1 << v)) continue;
            dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], 
                                         dp[mask][u] + dist[u][v]);
        }
    }
}
```

#### 2. 棋盘覆盖问题

```cpp
int dp[1 << m]; // dp[mask]表示当前行被覆盖的状态为mask时的方案数

dp[0] = 1;
for (int i = 0; i < n; ++i) {
    for (int mask = (1 << m) - 1; mask >= 0; --mask) {
        if (!dp[mask]) continue;
        for (int new_mask = 0; new_mask < (1 << m); ++new_mask) {
            if (mask & new_mask) continue;
            if (new_mask中有连续奇数个1) continue; // 根据具体问题调整
            dp[mask | new_mask] += dp[mask];
        }
    }
}
```

### 六、优化技巧
预处理合法状态：提前计算并存储所有可能的状态或状态转移

滚动数组：当状态转移只依赖前一层时，可以压缩空间

剪枝：在状态转移过程中跳过不可能达到的状态

双端BFS：对于对称性问题，可以从初始状态和目标状态同时搜索

### 七、注意事项
注意位运算的优先级，必要时加括号

当n较大时（如n>20），状态空间可能过大（2^20≈1e6，2^25≈3e7）

考虑状态表示的对称性以减少状态数量

调试时可以打印二进制形式的状态辅助理解

### 八、复杂度分析
时间复杂度通常为O(n * 2^n)，空间复杂度O(2^n)或O(n * 2^n)

### 九、扩展应用
二维的状压DP，如（玉米地）

正在渲染内容...