偶尔碰到这题，简单数位DP题，然而我已生疏了……
这次算是重新想到的，看来对DP的理解有增进了……
dp[i][j][k]，表示前i为，mod为j，是否出现2、3、5的剩下的数位可组成的数字。答案就是dp[len][0][0]
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define LL long long LL dp[20][7][2];int num[20];LL dfs(int len, int mod, bool one, int show, bool flag){if(len == 0){if(show == 1 && mod == 0){dp[len][mod][show] = 1;}else dp[len][mod][show] = 0;return dp[len][mod][show];}if(!flag && dp[len][mod][show] != -1) return dp[len][mod][show];int up = flag ? num[len]:9;LL ans = 0, tmp = show;for(int i = 0; i <= up ; i++){if(one && i == 8) continue;if(i == 2 || i == 3 || i == 5) tmp = (show | 1);//cout <<" tmp = " << tmp << endl;ans += dfs(len - 1, (mod * 10 + i)%7, i == 1?true:false, tmp, (flag && i == up) ? true: false);tmp = show;//printf("%I64d====%d\n", ans, i);}dp[len][mod][show] = ans;return ans;}long long slove(LL n){int len = 0;LL tmp = n;while(tmp){num[++len] = tmp % 10;tmp /= 10;}//printf("%I64d\n", n);dfs(len, 0, false, 0, true);return dp[len][0][0];}int main(){long long l, r;int T;scanf("%d", &T);while(T--){memset(dp, -1, sizeof(dp));scanf("%I64d%I64d", &l, &r);printf("%I64d\n", slove(r) - slove(l - 1));}return 0;}
