题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3652
题目大意：给你一个数R，让你求[1, R]有多少个数，包含连续的13数字并且能够整除13。

包含13这个状态很好处理，前面的那道不要62就处理过这种情况。但是这个整除的状态就比较难表示。

后来学习了一种表示方法：用余数表示。例如：143

pos=2时 mod2=1
pos=1时 mod1=(mod2 * 10+4)%13=1
pos=0时 mod0=(mod3 * 10+3)%13=0

所以143能被13整除。

这利用了mod的性质:

( preSum * 10^pos + next ) % MOD

= ( preSum * 10 ^ pos % MOD + next % MOD )

所以整除转化成余数就可以保存状态了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int a[20];
LL dp[20][20][3];

//ok:0 没有出现13 并且上一位不是1
//ok:1 没有出现13 并且上一位是1
//ok:2 出现过13

LL dfs(int pos, int mod, int ok, int mt)
{
    if(pos==-1)
    {
        if(ok==2&&mod==0)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }

    if(!mt&&dp[pos][mod][ok]!=-1)
    {
        return dp[pos][mod][ok];
    }

    int Len=mt?a[pos]:9;
    LL ans=0;
    for(int i=0;i<=Len;i++)
    {
        if(i==1)
        {
            ans+=dfs(pos-1, (mod*10+i)%13, ok==2?2:1, mt&&i==a[pos]);
        }
        else if(i==3)
        {
            ans+=dfs(pos-1, (mod*10+i)%13, ok==2?2:(ok==1?2:0), mt&&i==a[pos]);
        }
        else
        {
            ans+=dfs(pos-1, (mod*10+i)%13, ok==2?2:0, mt&&i==a[pos]);
        }
    }

    if(!mt)
    {
        dp[pos][mod][ok]=ans;
    }

    return ans;
}

LL slove(LL x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }

    return dfs(pos-1, 0, 0, true);
}

int main()
{
    LL R;
    memset(dp, -1, sizeof(dp));
    while(scanf("%lld",&R)!=EOF)
    {
        printf("%lld\n", slove(R));
    }

    return 0;
}