数位DP

· · 个人记录

数位DP

本来看见10^{18}就想矩阵快速幂的，现在又来了个数位DP

适用情况

数位DP用来解决的问题一般具备如下条件

  1. 要求统计满足一定条件的数的数量（即，最终目的为计数）；
  2. 这些条件经过转化后可以使用「数位」的思想去理解和判断；
  3. 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
  4. 上界很大（比如10^{18} ），暴力枚举验证会超时。

基本原理

考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。

但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位。

所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推/DP 的方式进行状态转移。

例题

Round Numbers S

题目大意

求区间[l,r]中有多少个数满足，二进制下0的个数不小于1的个数。

题解

#include<iostream>
#include<cstdio>
#define R register
using namespace std;
int l,r,len,a[40],dp[40][100];
inline int read(){
    int a=0,b=1;
    char s=getchar();
    while(s<48||s>57){
        if(s=='-') b=-1;
        s=getchar();
    }
    while(s>=48&&s<=57)
        a=(a<<1)+(a<<3)+s-48,s=getchar();
    return a*b;
}
//wz当前所在数位，limit此时是否有数量限制（即是否能取1）
//opt当前位之前是否都为0，cha 0的个数与1的个数之差，为了避免负数而全部加30
int dfs(int wz,int limit,int opt,int cha){
    if(!wz) return cha>=30;//扫完了，看0的个数是否大于1的个数
    if(!limit&&!opt&&dp[wz][cha]) return dp[wz][cha];//无限制，考虑记忆化
    int up=limit?a[wz]:1;//如果有限制，那么这一位最多取a[wz]，无限制也最多取1
    int ans=0;
    //往后递归，如果填的数达到最大值就下传limit，如果这一位是0就下传opt，前导0不计入差值
    for(R int i=0;i<=up;i=-~i)
        ans+=dfs(wz-1,limit&&(i==a[wz]),opt&&(i==0),cha+(i==0?(opt?0:1):-1));
    if(!limit&&!opt) dp[wz][cha]=ans;
    return ans;
}
inline int solve(int x){
    len=0;
    while(x) a[++len]=x&1,x>>=1;
    dfs(len,1,1,30);
}
int main(){
    l=read(),r=read();
    printf("%d\n",solve(r)-solve(l-1));//[l,r]中的个数=[1,r]的-[1,l]的
    return 0;
}