/*
数位dp
题意：找到1-n之间包括13这个子串而且可以整除13的数
解：刚開始dp[N][N][2]这里的2用来记录是否为13表示当前位是否为13，我把上一位为1当前位为13和上一位部位1
这样的情况在数组中没有记录。
*/
#include<stdio.h>
#include<string.h>
#define N 14
int dp[N][N][3];
int digit[N];
int dfs(int len,int mod,int cnt,int ok) {
if(!len) {
if(mod==0&&cnt==2)return 1;
return 0;
}
if(!ok&&dp[len][mod][cnt]!=-1)
return dp[len][mod][cnt];
int ans=0,i,maxx=ok? digit[len]:9;
for(i=0;i<=maxx;i++) {
if(cnt==2||(cnt==1&&i==3))
ans+=dfs(len-1,(mod*10+i)%13,2,ok&&i==maxx);
else
if(i==1)//刚開始这里推断条件写成if(cnt==0&&i==1)这样是不正确的由于漏掉了一种情况(i==1&&cnt==1)
ans+=dfs(len-1,(mod*10+i)%13,1,ok&&i==maxx);
else
ans+=dfs(len-1,(mod*10+i)%13,0,ok&&i==maxx);
}
if(!ok)
dp[len][mod][cnt]=ans;
return ans;
}
int f(int n) {
int len=0;
while(n) {
digit[++len]=n%10;
n/=10;
}
return dfs(len,0,0,1);
}
int main() {
int n;
memset(dp,-1,sizeof(dp));
while(scanf("%d",&n)!=EOF) {
printf("%d\n",f(n));
}
return 0;}
<pre name="code" class="cpp">/*
我原来的思路，刚開始写的时候少开了一维记录pre的情况
*/
#include<stdio.h>
#include<string.h>
#define N 14
int dp[N][N][2][2];
int digit[N];
int dfs(int len,int mod,int pre,int cnt,int ok) {
if(!len) {
if(mod==0&&cnt==1)return 1;
return 0;
}
if(!ok&&dp[len][mod][pre][cnt]!=-1)
return dp[len][mod][pre][cnt];
int ans=0,i,maxx=ok? digit[len]:9;
for(i=0;i<=maxx;i++) {
if(cnt||(pre&&i==3))
ans+=dfs(len-1,(mod*10+i)%13,i==1,1,ok&&i==maxx);
else
ans+=dfs(len-1,(mod*10+i)%13,i==1,0,ok&&i==maxx);
}
if(!ok)
dp[len][mod][pre][cnt]=ans;
return ans;
}
int f(int n) {
int len=0;
while(n) {
digit[++len]=n%10;
n/=10;
}
return dfs(len,0,0,0,1);
}
int main() {
int n;
memset(dp,-1,sizeof(dp));
while(scanf("%d",&n)!=EOF) {
printf("%d\n",f(n));
}
return 0;}