HDU3652 B-number

Description

求小于等于n的数中满足含有13且各位数字和mod13等于0的数的个数。（n<=1e9)

数位DP

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int dp[20][20][20][3],num[20];

inline int dfs(int now,int pre,int sum,int have,bool limit)
{
    if(now==0&&sum==0&&have==1) return 1;
    if(now==0) return 0;
    if(!limit&&dp[now][pre][sum][have]!=-1) return dp[now][pre][sum][have];
    int up=9,ans=0;
    if(limit) up=num[now];
    for(register int i=0;i<=up;++i)
        ans+=dfs(now-1,i,(sum*10+i)%13,have||(pre==1&&i==3),limit&&(i==num[now]));
    if(!limit) dp[now][pre][sum][have]=ans;
    return ans;
}

inline int solve(int k)
{
    int pos=0;
    while(k>0)
    {
        num[++pos]=k%10;
        k/=10;
    }
    return dfs(pos,0,0,0,true);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    int n;
    while(scanf("%d",&n)!=EOF) printf("%d
",solve(n));
     return 0;
}