每天一个数位DP，做熟练了为止


题目链接：HDOJ3652

题意：求【1，n】中，能够被13整除且含有“13”字符串的数的个数


分析：

首先把问题变简单一点，含有“13”字符串怎么处理？废话了嘛，就是模板啊，处理过49，处理过62，一个套路

那么怎么在这个基础上处理被13整除呢？

很简单，加一维变量，mod为从高位到当前位的数值和，模13的余数


即：dp【pos】【status】【mod】添加一维dp变量

然后上模板


__int64 n;
int digit[20];
__int64 dp[20][5][15];

__int64 dfs(int pos,int status,int mod,bool flag){
	if (pos==0) return (status==2&&mod==0);
	if (flag&&dp[pos][status][mod]!=-1) return dp[pos][status][mod];
	int num=flag?9:digit[pos];
	__int64 ans=0;
	for(int i=0;i<=num;i++){
		int nowmod=(mod*10+i)%13;
		if (status==2||(status==1&&i==3)) ans+=dfs(pos-1,2,nowmod,flag||i<num);
		else if (i==1) ans+=dfs(pos-1,1,nowmod,flag||i<num);
		else ans+=dfs(pos-1,0,nowmod,flag||i<num);
	}
	if (flag) dp[pos][status][mod]=ans;
	return ans;
}

__int64 calc(__int64 n){
	//标准格式
	//将n分解成各个数位，从高到低
	memset(digit,0,sizeof(digit));
	int pos=0;
	while(n){
		digit[++pos]=n%10;
		n/=10;
	}
	return dfs(pos,0,0,0);
}

int main(){
	//input;
	memset(dp,-1,sizeof(dp));
	while(scanf("%I64d",&n)!=EOF)
		printf("%I64d\n",calc(n));
	return 0;
}