【分析】
挺神奇(套路)的表示状态
感觉自己有点入门了…（但愿不是错觉）
dp[i][j][k][l]表示i位数字，最高位为j，除以13的余数为k，且包含13的数字个数
【代码】
//hdu 3652 数位dp #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define ll long long#define M(a) memset(a,0,sizeof a)#define fo(i,j,k) for(i=j;i<=k;i++)using namespace std;int n,m;ll dp[15][10][15][2],pw[15],digit[15];inline ll work(int n){ ll i,j,k,len=0,ans=0,now=0,flag=0; memset(digit,0,sizeof digit); while(n) digit[++len]=n%10,n=n/10; for(i=len;i>=1;i–) { fo(j,0,digit[i]-1) { ans+=dp[i][j][(13-now)%13][1]; if(flag || (digit[i+1]==1 && j==3)) ans+=dp[i][j][(13-now)%13][0]; } now=(now+digit[i]*pw[i-1])%13; if(digit[i+1]==1 && digit[i]==3) flag=1; } return ans;}int main(){ ll i,j,k,x; dp[0][0][0][0]=1; pw[0]=1; fo(i,1,12) pw[i]=pw[i-1]*10; fo(i,1,10) fo(j,0,9) fo(k,0,12) fo(x,0,9) //上一位的数字 { int tmp=(k-j*pw[i-1]%13+13)%13; if(!(j==1 && x==3)) dp[i][j][k][0]+=dp[i-1][x][tmp][0]; dp[i][j][k][1]+=dp[i-1][x][tmp][1]; if(j==1 && x==3) dp[i][j][k][1]+=dp[i-1][x][tmp][0]; } while(scanf(“%d”,&n)!=EOF) printf(“%lld\n”,work(n+1)); return 0;}