UESTC 884 方老师的专题讲座 --数位DP

时间：2021-09-06 05:58:12

定义:cnt[L][K]表示长度为L,最高位为K的满足条件C的个数。

首先预处理出cnt数组，枚举当前长度最高位和小一个长度的最高位，如果相差大于2则前一个加上后一个的方法数。

然后给定n，计算[1,n-1]中满足条件C的数的个数。

设有K位数，则不足K位的累加，然后枚举K位数的情况，从高位到低位枚举，每次枚举到比该位小1的数，注意：如果某时刻该数中有两位相差大于2，则再枚举下去已经没有意义，因为以后的数再也不会满足条件C，这时退出即可。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <string>

#define Mod 1000000007

#define ll long long

using namespace std;

#define N 100007

ll cnt[][];  //cnt[L][K]:长度为L,最高位为K的满足条件C的数的个数

ll NUM[];

ll DP(ll a)    //[1,n-1]

{

    int i,j,K;

    int pre,head;

    ll res = ;

    K = ;

    while(K <=  && NUM[K] <= a)

        K++;

    K--;

    //cout<<"K is "<<K<<endl;

    for(i=;i<K;i++)     //所有小于a长度的长度

        for(j=;j<=;j++)   //所有首位

            res += cnt[i][j];

    head = a/NUM[K];      //数a的首位

    for(i=;i<head;i++)    //从1开始（不含前导0）

        res += cnt[K][i];

    a %= NUM[K];   //去除首位

    pre = head;    //多一位的首位

    for(i=K-;i>=;i--)  //长度逐次递减,高位到低位

    {

        head = a/NUM[i];

        for(j=;j<head;j++)   //小于a的当前位的数做首位

            if(abs(pre-j) >= )

                res += cnt[i][j];

        if(abs(head-pre) < )   //如果前面某两位出现差小于2，再枚举后面的数就没意义了，因为无论如何都不会满足了。

            break;

        pre = head;

        a %= NUM[i];  //一个一个去除

    }

    return res;

}

int main()

{

    int i,j,l,k;

    ll a,b;

    j = ;

    NUM[j++] = 0LL;

    for(i=;i<=;i++)

        NUM[j++] = (ll)pow(,i-);

    //for(i=0;i<j;i++)

        //cout<<NUM[i]<<" ";

    //cout<<endl;

    memset(cnt,,sizeof(cnt));

    for(k=;k<=;k++)

        cnt[][k] = ;

    for(l=;l<=;l++)

    {

        for(i=;i<=;i++)   //长度为l时的首位

        {

            for(k=;k<=;k++)   //长度为l-1时的首位

            {

                if(abs(k-i) >= )

                    cnt[l][i] += cnt[l-][k];

            }

        }

    }

    for(k=;k<=;k++)  //10^18

        if(abs(-k) >= )

            cnt[][] += cnt[][k];

    while(scanf("%lld%lld",&a,&b)!=EOF)

    {

        printf("%lld\n",DP(b+)-DP(a));

    }

    return ;

}

相关文章