1.【HDOJ2089】
题意：求区间内不出现4和62的数的个数
解法：模板题
2.【HDOJ3555】
题意：求区间内不出现49的数的个数
解法：模板题
3.【HDOJ5179】
题意：对于一个十进制数，把每一位拆出来变成一个数组，要求数组右边的数都小于等于左边的数，且左数能整除右数。求区间内满足条件的个数
解法：dp[i = 20][j = 10]: j为前一位上的数
按要求转移即可，要考虑前导零，注意防止%0的情况出现
4.【HDOJ3652】
题意：求区间内含13或者是13倍数的数的个数
解法：dp[i = 20][j = 13][k = 3]: j为对13的余数，k为状态(0: 前一位不是1 | 1: 前一位是1 | 2: 前面出现过13)
最后当j为0，k为2时加入计数，计算不含13并且不是13倍数的数
输出时为N + 1 - solve(N) (0也在统计内)
5.【HDOJ3709】
题意：定义平衡数，以某一数位作为原点，左边数位上数字 × 距离之和与右边数位上的相等。求区间内平衡数的个数
解法：dp[i = 20][j = 5000][k = 20]: j为左边数位权值之和，k为枚举的原点
需要枚举原点，然后统计左边权值的减去右边的权值最后是否为零，由于 0 对于每个枚举位置都会被统计，最后要再减去枚举次数 - 1个重复的0
6.【HDOJ6148】
题意：对于一个十进制数，要求从左到右的数位没有出现先递增接着递减的情况，求区间内满足条件的个数
解法：dp[i = 105][j = 10][k = 2]: j为前一个数，k表示前面是否已出现递增
按要求转移即可，要考虑前导零，这题的0是不合法的，额外减1就行了，注意数据范围10^100
7.【HDOJ5898】
题意：对于一个十进制数，要求数位中奇数段长度都为偶数，偶数段长度都为奇数，求区间内满足条件的个数
解法：dp[i = 20][j = 10][k = 20]: j为前一个数，k为前一个数所属段的长度
要考虑前导零，转移时，当前数位若与前一位奇偶相反，表示前一段已结束，判断长度是否满足要求剪枝，并重置k为1继续向下枚举，最后统计时还要再判断一次j与k，奇偶相反则加入统计
8.【HDOJ4734】
题意：定义：F(x) = An * 2^n-1 + An-1 * 2^n-2 + ... + A2 * 2 + A1 * 1，Ai是十进制数位，求区间内满足F(i)<=F(a)的i的个数
解法：dp[i = 20][j = 20000]: j表示枚举到当前位时，在满足条件情况下后面的数位还能有多少权值（初始值为F(a)）
最后当j >= 0加入计数，中间状态若j已经小于0则可剪枝
9.【HDOJ4352】
题意：求区间内数位从左到右满足LIS = m的数的个数
解法：dp[i = 20][j = 1 << 10][k = 11]: j状态压缩表示当前LIS状态，k表示所求LIS长度（不加k会导致每组数组要重新初始化，超时）
要考虑前导零，在数位上跑nlogn的LIS
int updateState(int state, int digit) {
// i=digit严格递增，状态压缩无法计算不减递增
for (int i = digit; i <= 9; i++) {
if (state & (1 << i)) {
state ^= (1 << i);
break;
}
}
return state | (1 << digit);
}
int getLIS(int state) {
int cnt = 0;
while (state) {
if (state & 1) {
cnt++;
}
state >>= 1;
}
return cnt;
}
10.【HDOJ4507】
题意：求区间内和7无关的数字的平方和，结果对1e9+7取模
解法：dp[i = 20][j = 7][k = 7]: j表示整个数%7的余数，k表示数位和%7的余数
要求的是所有满足条件的数的平方和，要对一个数按照平方和公式拆分。
假设满足条件的数有234, 245, 266，那么
234^2 + 245^2 + 266^2 =
(200 + 34)^2 + (200 + 45)^2 + (200 + 66)^2 =
3 * 200^2 + 2 * 200 * (34 + 45 + 66) + (34^2 + 35^2 + 66^2)
因此在枚举到2的时候，表达式里未知的只有3, (34 + 45 + 66), (34^2 + 35^2 + 66^2)
结构体数组dp中记录三个值，cnt代表满足条件的数的个数，sum表示满足条件的数的求和，sum2表示满足条件的数的平方和
不带取模的转移方程：
ans.cnt += tmp.cnt
ans.sum += (tmp.sum + tmp.cnt * (i * p[pos]))
ans.sum2 += (tmp.cnt * (i * p[pos])^2 + 2 * (i * p[i]) * tmp.sum + tmp.sum2)
为了防止出现负数，输出要(solve(r) - solve(l - 1) + mod) % mod
11.【POJ3252】
题意：求区间内满足二进制下0的数位 >= 1的数位的数的个数
解法：dp[i = 32][j = 32][k = 32]: j表示0的个数，k表示1的个数
要考虑前导零，按照题意转移即可，注意j + len - pos < k时可剪枝
12.【HDOJ3886】
题意：给出一个字符串，只含/， -， \ ，要求一个数上的数位按相应字符上升、不变或下降（如12345554321符合/-\），求区间内满足条件的数的个数，输出时保留最后八位
解法：dp[i = 105][j = 10][k = 105]: j表示前一个数，k表示匹配到字符串哪个位置
要注意的点比较多：
① 输入数据可能有前导零，范围10^100
② 字符串数据的大整数减法（L - 1）
③ 输出时保留最后八位，即对1e8取模，同时按照指定格式输出printf("%08lld\n",(solve(r) - solve(l) + mod) % mod);
④ 对每组数据都要初始化dp，因为要匹配的字符串变了
⑤ 枚举时要考虑前导零，只能在无前导零状态时进行匹配
⑥ 当能匹配下一个字符时，尽量先匹配，如果不能再判断是否符合之前的字符