关于数位dp

上周学了数位dp，本来想上周周末写一下这个总结，怎奈没有安排上时间
安排 @TOC

关于题目小结

关于所做过题目的总结以及一些个人想法。

不要62 HDU - 2089

这个题目给我的收获是知道怎么去处理出现连续的两个位数和出现单个位数的特殊情况。
对于这种连续两个位数的情况直接使ispre是上一位是x，i是下一位。
单个位数的话限制条件就是i。
然后，直接上模板做就可以了。比如这题。

HDU - 3555 Bomb

还有这个题目

HDU - 3652

关于这道题目限制条件就是出现13和数不能被13整除的个数。
又get了一个新的知识，就是对于被某个数整除的情况，
对于被整除， modx=mod*10+i;//这个可以求出每一个数字。
简单

说到着，这些数位dp简单题目学了数位dp的人肯定都可以做，因为（这个dp的束缚条件比较少，也比较好处理。）
我不想就仅仅如此，我还想更上一层楼，那么对于这个，还需要自己做更多的题目。

ll dfs(int pos,int mod,int have,int  limit)
{
   
    int modx,havex;
    if(pos==0)
    {
   
        return mod==0&&have==2;
    }
    if(!limit&&dp[pos][mod][have]!=-1)
        return dp[pos][mod][have];
    ll ans=0;
    int Max=limit?num[pos]:9;
    for(ll i=0; i<=Max; i++)
    {
   
        modx=(mod*10+i)%13;//关于位数
        havex=have;
        if(have==0&&i==1)
            havex=1;
        if(have==1&&i!=1)
            havex=0;
        if(have==1&&i==3)
            havex=2;
        ans+=dfs(pos-1,modx,havex,(limit&&i==Max));
    }
    if(!limit)
        dp[pos][mod][have]=ans;
    return ans;
}

简单比如这道题

追梦之人

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
ll dp[500][9000][3];
ll num[50];
ll dfs(int pos,ll mod,int have,int  limit)
{
   
    ll modx;
    if(pos==0)
    {
   
        return mod%7!=0;
    }
    if(!limit&&dp[pos][mod][have]!=-1)
        return dp[pos][mod][have];
    ll ans=0;
    int Max=limit?num[pos]:9;
    for(int i=0; i<=Max; i++)
    {
   
        modx=(mod*10+i)%7;
        if(i==7)
            continue;
        ans+=dfs(pos-1,modx,i==7,(limit&&i==Max));
    }
    if(!limit)
        dp[pos][mod][have]=ans;
    return ans;
}
ll jj(ll x)
{
   
    int cnt=0;
    while(x)
    {
   
        num[++cnt]=x%10;
        x/=10;
    }
    return dfs(cnt,0,1,1);
}
int main()
{
   
    ll a;
    int t;
    cin>>t;
    memset(dp,-1,sizeof(dp));
    while(t--)
    {
   
        scanf("%lld",&a);
        printf("%lld\n",jj(a));
    }
    return 0;
}

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
int dp[18][2][2];
int  num[18];
int dfs(int pos,int ispre,int limit)
{
   
    if(pos==0)
        return 1;
    if(dp[pos][ispre][limit]!=-1)
    {
   
        return dp[pos][ispre][limit];
    }
    int sum=0;
    int up=limit?num[pos]:9;
    for(int i=0; i<=up; i++)
    {
   
        if(ispre&&i==2)
            continue;
        if(i==4)
            continue;
        sum+=dfs(pos-1,i==6,limit&&i==up);
    }
    return dp[pos][ispre][limit]=sum;
}
int solve(int x)
{
   
    mem(dp,-1);
    int pos=0;
    while(x)
    {
   
        num[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,1);
}
int main()
{
   
    int ri,le;
    while(scanf("%d%d",&le,&ri)&&ri+le)
    {
   
        printf("%d\n",solve(ri)-solve(le-1));
    }
    return 0;
}