题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3652
题意：给你一个n,为比n小的能整除13并数字中有13的数有多少个
题解：记忆化搜索：记dp[i][j][k][l]为当前为第i位i+1位的数为j，余数为k，是否含有13的数的个数，然后搜索下去就得出答案了
#include<cstdio>
#include<cstring>
#define F(i,a,b) for(int i=a;i<=b;i++) int dp[][][][],n,dig[],len; int dfs(int pos,int pre,int mod,bool have,bool inf){
if(!pos)return (have&&!mod);
if(!inf&&dp[pos][pre][mod][have]!=-)return dp[pos][pre][mod][have];
int end=inf?dig[pos]:,ans=;
F(i,,end)if(pre==&&i==)ans+=dfs(pos-,i,(mod*+i)%,,inf&&(i==dig[pos]));
else ans+=dfs(pos-,i,(mod*+i)%,have,inf&&(i==dig[pos]));
if(!inf)dp[pos][pre][mod][have]=ans;
return ans;
} int main(){
memset(dp,-,sizeof(dp));
while(~scanf("%d",&n)){
for(len=;n;)dig[++len]=n%,n/=;
printf("%d\n",dfs(len,,,,));
}
return ;
}