状压DP，数位DP
题单介绍
# 下面两个链接是我看了一圈后觉得不错的，一定要看
## [状态压缩入门](https://www.luogu.com.cn/blog/yijan/zhuang-ya-dp)
## [数位dp](https://www.luogu.com.cn/blog/virus2017/shuweidp)
# 【模板】
### 代码模板
```
【模板】
ll dfs(int pos,int pre,int st,……,int lead,int limit)//记搜
{
if(pos>len) return st;//剪枝
if((dp[pos][pre][st]……[……]!=-1&&(!limit)&&(!lead))) return dp[pos][pre][st]……[……];//记录当前值
ll ret=0;//暂时记录当前方案数
int res=limit?a[len-pos+1]:9;//res当前位能取到的最大值
for(int i=0;i<=res;i++)
{
//有前导0并且当前位也是前导0
if((!i)&&lead) ret+=dfs(……,……,……,i==res&&limit);
//有前导0但当前位不是前导0，当前位就是最高位
else if(i&&lead) ret+=dfs(……,……,……,i==res&&limit);
else if(根据题意而定的判断) ret+=dfs(……,……,……,i==res&&limit);
}
if(!limit&&!lead) dp[pos][pre][st]……[……]=ret;//当前状态方案数记录
return ret;
}
ll part(ll x)//把数按位拆分
{
len=0;
while(x) a[++len]=x%10,x/=10;
memset(dp,-1,sizeof dp);//初始化-1（因为有可能某些情况下的方案数是0）
return dfs(……,……,……,……);//进入记搜
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&l,&r);
if(l) printf("%lld",part(r)-part(l-1));//[l,r](l!=0)
else printf("%lld",part(r)-part(l));//从0开始要特判
}
return 0;
}
```
# [蓝书的状压dp](http://ybt.ssoier.cn:8088/index.php)
#### 0x13 状压dp
将状态压缩成一个任意进制的数进行dp，适用于数据范围小的dp
[P3052 [USACO12MAR]Cows in a Skyscraper G](https://www.luogu.com.cn/problem/P3052) 状压dp+枚举状态的子集
[P1896 [SCOI2005]互不侵犯](https://www.luogu.com.cn/problem/P1896)
[P1879 [USACO06NOV]Corn Fields G](https://www.luogu.com.cn/problem/P1879)
[P2704 [NOI2001]炮兵阵地](https://www.luogu.com.cn/problem/P2704) 状压dp+空间优化
[P3959 宝藏](https://www.luogu.com.cn/problem/P3959) 状压dp，按层转移
[P2150 [NOI2015]寿司晚宴](https://www.luogu.com.cn/problem/P2150) 隐藏的数据范围
[P2566 [SCOI2009]围豆豆](https://www.luogu.com.cn/problem/P2566) 状压dp+计算几何技巧
# 加入大量蓝题练习
- [P1879 [USACO06NOV]Corn Fields G](https://www.luogu.com.cn/problem/P1879)
- [P4011 孤岛营救问题](https://www.luogu.com.cn/problem/P4011)
- [P1283 平板涂色](https://www.luogu.com.cn/problem/P1283)
- [P4877 [USACO14FEB]Cow Decathlon G](https://www.luogu.com.cn/problem/P4877)
- [P6289 [COCI2016-2017#1] Vještica](https://www.luogu.com.cn/problem/P6289)
- [P1896 [SCOI2005] 互不侵犯](https://www.luogu.com.cn/problem/P1896)
- [P3087 [USACO13NOV]Farmer John has no Large Brown Cow S](https://www.luogu.com.cn/problem/P3087)
- [P2591 [ZJOI2009]函数](https://www.luogu.com.cn/problem/P2591)
- [P2167 [SDOI2009]Bill的挑战](https://www.luogu.com.cn/problem/P2167)
- [P8394 [BalticOI 2022 Day2] Boarding Passes](https://www.luogu.com.cn/problem/P8394)
- [P3694 邦邦的大合唱站队](https://www.luogu.com.cn/problem/P3694)
- [P8756 [蓝桥杯 2021 省 AB2] 国际象棋](https://www.luogu.com.cn/problem/P8756)
---
棋盘上还有按格转移的状压dp，可以节省一点时间复杂度，代码量较大
[「九省联考 2018」一双木棋](https://loj.ac/p/2471)
[P3272 [SCOI2011]地板](https://www.luogu.com.cn/problem/P3272) 插头dp入门题
[P3190 [HNOI2007]神奇游乐园](https://www.luogu.com.cn/problem/P3190) 也是插头dp入门题
[P5056 【模板】插头dp](https://www.luogu.com.cn/problem/P5056) 哈密尔顿回路，比较困难的插头dp
[P4262 [Code+#3]白金元首与莫斯科](https://www.luogu.com.cn/problem/P4262) 带有技巧性的插头/轮廓线dp
[P2337 [SCOI2012]喵星人的入侵](https://www.luogu.com.cn/problem/P2337) 复杂的插头dp
---
#### 0x14 数位dp
对于数进行dp
[P2657 [SCOI2009]windy数](https://www.luogu.com.cn/problem/P2657)
[P4124 [CQOI2016]手机号码](https://www.luogu.com.cn/problem/P4124)
[P2602 [ZJOI2010]数字计数](https://www.luogu.com.cn/problem/P2602)
↑都是数位dp入门题↑
[P2481 [SDOI2010]代码拍卖会](https://www.luogu.com.cn/problem/P2481) 带有技巧性的数位dp
- [P6218 [USACO06NOV] Round Numbers S](https://www.luogu.com.cn/problem/P6218)
- [P2657 [SCOI2009] windy 数](https://www.luogu.com.cn/problem/P2657)
- [P4124 [CQOI2016]手机号码](https://www.luogu.com.cn/problem/P4124)
- [P2602 [ZJOI2010] 数字计数](https://www.luogu.com.cn/problem/P2602)
加入海量蓝黑题
- [P4317 花神的数论题](https://www.luogu.com.cn/problem/P4317)
# [先做蓝书上的配套练习](http://ybt.ssoier.cn:8088/index.php)
- **重要变动：此题删除，改为下题**
[~~P8688 [蓝桥杯 2019 省 A] 组合数问题~~](https://www.luogu.com.cn/problem/P8688)
- **重要变动：上题删除，改为此题**
[P6669 [清华集训2016] 组合数问题](https://www.luogu.com.cn/problem/P6669)
- [P7717 「EZEC-10」序列](https://www.luogu.com.cn/problem/P7717)
//先放一放- [P8766 [蓝桥杯 2021 国 AB] 异或三角](https://www.luogu.com.cn/problem/P8766)
- [P2518 [HAOI2010]计数](https://www.luogu.com.cn/problem/P2518)
- [P4127 [AHOI2009]同类分布](https://www.luogu.com.cn/problem/P4127)
- [P3281 [SCOI2013]数数](https://www.luogu.com.cn/problem/P3281)
- [P3311 [SDOI2014] 数数](https://www.luogu.com.cn/problem/P3311)
- [P7802 [COCI2015-2016#6] SAN](https://www.luogu.com.cn/problem/P7802)