题目链接 题意：给出n,问[1,n]中，满足包含“13”且这个数（不是各位的和）能被13整除的数的个数。 思路：依然是数位dp..不过有一个小tip。。 由于包含13的情况非常难考虑（包含一个“13”，两个“13”.....) 所以要从反面考虑，即不包含13的情况。 但是由于还有另一个条件。 做法是把能被13整除的数考虑成全集U,然后在U中做分划，一部分是含13的，另一部分是不含13的。 这样我们要求两个答案，一个是能被13整除的，另一个是能被13整除并且不含13的，相减即为题目所求。 /* *********************************************** Author :111qqz Created …

题目链接 题意：求一个区间内所有位数字之和能被10整除的数的个数。 思路：数位dp，dfs要一个参数记录从最高位到现在的pos位置的数字之和的结果。 dp[i][j] 表示长度为i，和为j的方案数。 记得开long long ，然而我开了那么多long long 忘了dp 的long long 结果wa到死。。果然大早上不清醒吗== /* *********************************************** Author :111qqz Created Time :2016年03月16日 星期三 08时10分19秒 File Name :code/hdu/4722.cpp …

题目链接 题意：不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？ 思路：数位dp 这道题的特点是前面不允许前导0，也就是说，如果第i位前面全是0的话，这个数就变成了i位数，i就变成了最高位，而最高位没有前面的数（**如果这里不考虑不允许前导0这个因素而把前面的一个数认为成是0就错了） **最高位的数可以直接取。 还有记忆化调用以及存储的时候也要注意...只有当位数相同的时候转移才有意义。 具体的方法是dfs中多了一个prehasnonzero的bool变量，就是字面意思，判断当前位置前面的位置是够存在一个非0的值。 /* …

题目链接 题意:问从1到n的所有数中，有多少个数含有数字串“49” 思路：和上一道不要62很像，但是由于是要统计有49的，但是有49的情况实在太多了，正难则反，用减法定理反过来考虑，先统计出不含49的数的个数，这样就和不要62一样了，然后再用总数减。 /* *********************************************** Author :111qqz Created Time :2016年03月15日 星期二 19时32分24秒 File Name :code/hdu/3555.cpp ************************************************ */ …

题目链接 题意：问区间[n,m]中，不含数字4，也不含数字串“62”的所有数的个数。 思路：可以转化成求区间[0,x] 第一次接触数位dp,参考了这几篇博客。 不要62（数位dp）解题报告 解题报告2 解题报告3 比较重要的前提： ¨对于一个小于n的数，肯定是从高位到低位出现某一位<n的那一位。 ¨如 n = 58 n为十进制数。 ¨ x = 49 此时x的十位<n ¨ x = 51 此时x的个位<n ¨有了上述性质，我们就可以从高到低枚举第一次<n对应位是哪一位。 这样之前的位确定了，之后的位就不受n的限制即从00...0~99...9，可以先预处理 以及写成递归形式代码会简洁很 …

http://codeforces.com/problemset/problem/621/E 题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。 思路：数位dp.首先考虑b不是很大的一般情况。dp[i][j]表示处理到前i个块的时候结果为j的方案数。那么转移方程就是：**dp[i][(j_10+t)%x] = dp[i-1][j]_cnt[t] ** cnt[i]表示数字i出现的个数。 但是由于b很大（1E9）,所以需要用矩阵加速。 /* *********************************************** …

http://codeforces.com/contest/611/problem/B 题意：问a到b（1E18），二进制表示中只有一个0的数有多少个。 思路：这么大的数。。。不是有循环节就是math problems.  UD:20160318讲道理还有可能是数位dp好不好。。。 我们发现可以很容易得算出1到x的二进制表示中只有一个0 的数有多少个。 problem solved. 20160318update:学了数位dp后又看到这题。。。这题显然是数位dp啊。。。亏我找规律搞了出来2333. 后面附上数位dp方法AC的代码 /* *********************************************** …