数位统计DP
数位统计DP是一种有关数字的限制问题，一般问题形式类似于给定若干限制条件，求满足条件的第K小的数是多少，或者是询问区间\([L,R]\)内有多少满足要求的数字，对于这种类型的题，我们一般是先使用动态规划进行预处理，再运用类似与倍增优化DP的拼凑思想拼出最后的答案，亦或者是试填法
在这类题中，我们动态规划的状态设计一般是第一维是第\(i\)位数字，也就是阶段，后面几个维度一般是题目给的限制条件诞生的维度。
在做题过程中，这类型的题数据范围一般较大，但我们动态规划的算法复杂度大约为\(O(\log^k N)\)，至于拼凑与试填法的复杂度也是对数级别。这里的题很多与数学问题有所交叉，可以留意一下
做题套路
- 第K大，遇到这种问题的一般步骤是：动态规划预处理，再使用试填法，这个过程从高位考虑到低位，考虑当前位有多少种选择，填了当前位置之后有多少种方案(排名)，类似于平衡树求排名，我们从小到大枚举每一位的可能性，当我们可以填i的时候，如果填i之后的方案数不够K，那么i就不可以填，此时还要令K-=填i的方案数，注意一定得减，当找到的第一个方案数大于k的，这个方案就是我们应该选择的方案。这个的原理我们可以把整个所有的可能性看成一颗搜索树，每一个节点上都存着它有多少个叶子节点(对应方案数),我们要在这棵搜索树里找到从树根到排名为K的叶子节点的路径就是我们的答案,就与平衡树，权值线段树类似
- 求区间\([L,R]\)，这里因为是关于数的统计问题，是无后效性的，于是我们可以将其转换为前缀和运算,同样的，先进行动态规划预处理，用某些标志性的点进行拼凑出答案，当然我们也可以使用试填法的思想，只不过这个变成了统计方案而已
注意事项
- 时刻注意前导零的处理
- 强调不重不漏性
- 注意到动态规划的维度等等不要冗余
实战
例题1：装饰围栏
题目描述：
有 \(N\) 块长方形的木板，长度分别为 \(1,2,…,N\)，宽度都是\(1\)。
现在要用这 \(N\) 块木板组成一个宽度为 \(N\) 的围栏，满足在围栏中，每块木板两侧的木板要么都比它高，要么都比它低。
也就是说，围栏中的木板是高低交错的。
我们称“两侧比它低的木板”处于高位，“两侧比它高的木板”处于低位。
显然，有很多种构建围栏的方案。
每个方案可以写作一个长度为 \(N\) 的序列，序列中的各元素是木板的长度。
把这些序列按照字典序排序，如下图所示，就是 \(N=4\) 时，所有满足条件的围栏按照木板长度的字典序排序后的结果。
现在给定整数 C，求排名为 C 的围栏中，各木板的长度从左到右依次是多少。
\(1≤N≤20,\)
\(0<C<2^{63}\)
分析
很明显，N很小，C很大，这是一个第K大问题，我们按照套路来处理
- 设计动态规划：由于N很小，我们设计一个与N相关的状态，又因为这个涉及到高低排名，于是：设\(f[i,j,k]\)表示用\(i\)块木板，其中最左边木板的排名为\(j\)，身处\(k\)位(0低1高)的方案数，注意这里我们采用了类似排名的描述，而不是像长度为j这样的绝对性描述，这是因为在\(1\sim N\)中，排名为j和长度为j是等价的，且运用排名会使得我们状态转移非常轻松
- 进行动态规划预处理：有状态转移方程：
- 进行拼凑，具体步骤为：
(1). 假设我们已经填好了\(i-1\)块木板，记上一块木板的长度为\(last\)，位于\(k\)位，现在我们来考虑第\(i\)块木板
(2). 将\(k\)改为\(k\oplus 1\)即可得到当前木板的状态，然后我们从小到大枚举当前木板的实际长度和相对排名，尝试着使用这一个方案进行下一步
(3).设我们枚举的实际长度为\(len\)，相对排名为\(j\)，若\(f[n-i+1,j,k]<C\),令\(C=C-f[n-i+1,j,k]\)，继续尝试更大的\(j\)，否则这个\(j\)就是我们第\(i\)位的答案，进行下一位的枚举，直到最后就得出了答案，当然，最初的计算我们就直接判断\(k=0/1\)谁可以就可以了
#define int long long
int t,f[25][25][2],n,m,vis[25];
void init(){
f[1][1][0]=f[1][1][1]=1;
for(int i=2;i<=20;i++)
for(int j=1;j<=i;j++){
for(int k=1;k<j;k++)f[i][j][1]+=f[i-1][k][0];
for(int k=j;k<i;k++)f[i][j][0]+=f[i-1][k][1];
}
}//DP预处理
signed main(){
init();
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&m);
memset(vis,0,sizeof vis);
int last,k;
for(int j=1;j<=n;j++){
if(f[n][j][1]>=m){
last=j;
k=1;
break;
}
else m-=f[n][j][1];
if(f[n][j][0]>=m){
last=j;
k=0;
break;
}
else m-=f[n][j][0];
}//枚举第一位的情况
vis[last]=1;
printf("%lld",last);
for(int i=2;i<=n;i++){
k^=1;
int j=0;
for(int len=1;len<=n;len++){
if(vis[len])continue;
j++;
if(k==0&&len<last||k==1&&len>last){
if(f[n-i+1][j][k]>=m){
last=len;break;
}
else m-=f[n-i+1][j][k];
}
}
vis[last]=1;
printf(" %lld",last);
}
puts("");
}
return 0;
}
例题2：圆形数字
题目描述：
定义圆形数字如下：
把一个十进制数转换为一个无符号二进制数，若该二进制数中 0 的个数大于或等于 1 的个数，则它就是一个圆形数字。
现在给定两个正整数 a 和 b，请问在区间 [a,b] 内有多少个圆形数字。
分析
下面简称圆数
对于这道题，由于其与二进制有关，且要命的是这个二进制数不能含有前导零，且统计与0有关，这就逼迫我们不得不不记录前导零
那么对于这道题DP的状态就很明显了，设\(f[i,j]\)表示有\(i\)位的数里有\(j\)位是0（不含前导零）的数的数量
不难发现,这个数很容易抽象成：给定\(i\)个数，需要从中选出\(j\)个强制变成0，并且不能选择第一个数(为开头的1),很明显这就是一个组合数：\(f[i,j]=C_{i-1}^j\)，值得说的是，我们之所以以0来作为状态而不是1，是因为0相对于1更方便统计，因为组合数可以直接算，这里就不说了，当然也可以借\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)这个性质计算
那么我们下面讨论如何求\([1,a]\)中圆数的数量
考虑将a也拆成二进制，假设有\(tot\)位（\(1\sim tot\)），那么对于二进制表示下位数不足\(tot\)的部分就非常容易统计了
这部分的贡献一共是
很快可以算出来，然后我们考虑第\(tot\)位该怎么算
我们设\(a\)被二进制分解为\(a_{tot}a_{tot-1}…a_1\)（从高到低）
下面我们按从高到低的顺序进行拼凑
详细地说，我们设当前已经拼到了第\(i\)位，第\(tot\sim i+1\)一共有\(b\)个0，当前累计的答案为\(ans\)，那么我们就可以分类讨论了
- \(a_i=1\)，此时如果我们拼的数这一位取0，那么这个数后面无论再怎么取都一定不会超过\(a\)了，于是我们就可以把取0这一部分的答案累加上，写成公式是：
- \(a_i=0\),令\(b=b+1\)
一路统计下来我们就可以得到答案
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int num[55],cnt,tot,c[55][55],n,m,a,b;
#define f(i,j) c[i-1][j]
int solve(int a){
if(a==0)return 0;
tot=0;
while(a){
num[++tot]=a&1;
a>>=1;
}
int ans=0;
for(int i=1;i<tot;i++){
int k=(i+1)/2;
for(int j=k;j<=i;j++){
ans+=f(i,j);
}
}
int b=0;
for(int i=tot-1;i>0;--i){
if(num[i]==1){
for(int p=(tot+1)/2-b-1;p<=i;p++)ans+=f(i,p);//加上这一位填0的收益
}
else b++;
}
if(b>=(tot+1)/2)ans++;
return ans;
}
int main(){
for(int i=0;i<=30;i++)c[i][0]=1;
for(int i=1;i<=30;i++){
for(int j=1;j<=i;j++){
c[i][j]=c[i-1][j-1]+c[i-1][j];
}
}
scanf("%d%d",&a,&b);
printf("%d\n",-(solve(a-1)-solve(b)));
}
例题3：计数问题
这个题直接来一个数学做法
具体看我做题时的手稿：
至少我认为这还是比较好懂的，我们只需要把问题转换为前缀和来做就可以了，顺带的，\(1\sim9\)可以像我手稿上的直接做，但是0的时候注意前导零，具体看代码
int cnt(int n,int num) {
int ans=0,i=1,qd0=0;//前导零
while(i<=n){
int l=n/i,r=n%i;
ans+=(l+9-num)/10*i;
if(l%10==num)ans+=r+1;
if(!num)qd0+=i;
i*=10;
}
if(!num)qd0-=1;
return ans-qd0;
}
int main(){
int a,b;
while(~scanf("%d%d",&a,&b)&&a&&b) {
if(a>b)a^=b,b^=a,a^=b;//装逼必备，把式子展开你就懂了
for(int i=0;i<=9;++i)
printf("%d ",cnt(b,i)-cnt(a-1,i));
puts("");
}
return 0;
}