数位DP 学习笔记 | AlanSP's Blog

写在之前：

1.对于区间 $[X,Y]$ ，可利用统计 $[0,N]$ 中的答案 $f(N)$ ，则区间内的答案： $f(Y)-f(X-1)$ 。

2.从树的角度来考虑。

考虑边界 $N$ 可以拆分成 $B$ 进制数 $\overline{a_{n-1}a_{n-2}\dots a_0}$ 。

对于每一位，我们都可以按照当前位的数字为 $[0,a_{i}-1]$ 或 $a_i$ 分为两类。

对于前者，可以直接通过组合数计算。

对于后者，可以继续计算到 $a_0$ 。

最后答案为前者之和加上最后一种情况。

Problem 1.度的数量

Description：

求给定区间 [X,Y] 中满足下列条件的整数个数：这个数在B进制下‘1’的个数等于K。

Solution：

模板题，统计每一位的两个分支。

若该位为0，返回0。

该位为1，为 $C_{k-last}^i+1$ 。

该位大于1，1可以进入左边分支,为 $C^{i}_{k-last-1}$ 。

最后统计最右侧方案即可。

Code：

#include<bits/stdc++.h>
using namespace std;
const int N=35;
int f[N][N],l,r,K,B;
void Init()
{
    for(int i=0;i<=N;i++)
        for(int j=0;j<=i;j++)
            if(!j) f[i][j]=1;
            else f[i][j]=f[i-1][j]+f[i-1][j-1];
}
inline int dp(int n)
{
    if(!n) return 0;
    int res=0;
    int last=0;
    vector<int> nums;
    for(;n;n/=B) nums.push_back(n%B);
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        if(x)
        {
            res+=f[i][K-last];
            if(x>1)
            {
                if(last+1<=K) res+=f[i][K-last-1];
                break;//填了不是1的数不符合方案，不能是a*B^b
            }
            else
            {
                last++;
                if(last>K) break;
            }
        }
        if(K==last&&!i) res++;
    }
    return res;
}
int main()
{
    Init();
    scanf("%d%d%d%d",&l,&r,&K,&B);
    printf("%d",dp(r)-dp(l-1));
    return 0;
}

Problem 2.[ZJOI2010]数字计数

不放题面了，走这里。

算是很经典的一个题吧，不过这里采用直接暴力求前后数字。

然后直接统计计算。

大概136ms（吸氧负优化）。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define int long long
int l,r;
inline int dp(int n,int i)
{
    int res=0,num=0,bn=n;
    for(;bn;bn/=10) num++;
    for(int j=1;j<=num;j++)
    {
        int p=pow(10,j-1),l=n/p/10,r=n%p,now=n/p%10;
        if(i) res+=l*p;
        if(!i&&l) res+=(l-1)*p;//不算前导0
        if((now>i)&&(i||l)) res+=p;
        if((now==i)&&(i||l)) res+=r+1;//000+r->r+1
    }
    return res;
}
signed main()
{
    while(scanf("%lld%lld",&l,&r)&&l&&r)
    {
        if(l>r) swap(l,r);
        for(int i=0;i<=9;i++) printf("%lld ",dp(r,i)-dp(l-1,i));
        puts("");
    }
    return 0;
}

Problem 3.Loj#10164 数字游戏

Description：

科协里最近很流行数字游戏。

某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 123,446。

现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。

Solution:

和第一题类似。可以预处理出当前有i位数，最后一位是j的不降数的个数：

f[i][j]+=f[i-1][k](k\in[j,9])

之后直接转移即可，记住当n=0是也有一个不降数0。

last是上一个数的末尾，i+1是位数。

Code：

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int f[N][N],l,r;
void Init()
{
    for(int i = 0;i <= 9;i++) f[1][i]=1;
    for(int i=2;i<=N;i++)
        for(int j=0;j<=9;j++)
            for(int k=j;k<=9;k++)
                f[i][j]+=f[i-1][k];
}

inline int dp(int n)
{
    if(!n) return 1;
    vector<int> nums;
    while(n) nums.push_back(n%10),n/=10;
    int res=0,last=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        if(x<last) break;
        for(int j=last;j<x;j++)
            res+=f[i+1][j];
        last=x;
        
        if(!i) res++;
    }
    return res;
}

int main()
{
    Init();
    while(scanf("%d%d",&l,&r)!=EOF)
    {
        printf("%d\n",dp(r)-dp(l-1));
    }
    return 0;
}