题目链接：http://codeforces.com/problemset/problem/55/D
题意：给定区间，求区间内某数的所有数位能整除这个数本身的数的个数。
起初思路：dp(l,s,sum)表示这个数到l位，并且0~9出现的状态s，和为sum的时候的数字个数。发现这个sum不好处理，因为数字越来越大无法保证这个界限。用到一个性质：一个数能被一堆数整除，当且仅当这个数能被这堆数的最小公倍数整除。换句话说，我们统计这个数对1~9的最小公倍数取模，就能判断这个sum是否可以被各位数整除了。
结果MLE了，因为s这个状态统计了0~9 10个数的状态，所以占用空间是1024，因为0不用考虑，1一定能整除这个sum，所以删掉这两位。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define fr first 4 #define sc second 5 #define cl clear 6 #define BUG puts("here!!!") 7 #define W(a) while(a--) 8 #define pb(a) push_back(a) 9 #define Rint(a) scanf("%d", &a) 10 #define Rll(a) scanf("%I64d", &a) 11 #define Rs(a) scanf("%s", a) 12 #define Cin(a) cin >> a 13 #define FRead() freopen("in", "r", stdin) 14 #define FWrite() freopen("out", "w", stdout) 15 #define Rep(i, len) for(int i = 0; i < (len); i++) 16 #define For(i, a, len) for(int i = (a); i < (len); i++) 17 #define Cls(a) memset((a), 0, sizeof(a)) 18 #define Clr(a, x) memset((a), (x), sizeof(a)) 19 #define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 20 #define lrt rt << 1 21 #define rrt rt << 1 | 1 22 #define pi 3.14159265359 23 #define RT return 24 #define lowbit(x) x & (-x) 25 #define onecnt(x) __builtin_popcount(x) 26 typedef long long LL; 27 typedef long double LD; 28 typedef unsigned long long ULL; 29 typedef pair<int, int> pii; 30 typedef pair<string, int> psi; 31 typedef pair<LL, LL> pll; 32 typedef map<string, int> msi; 33 typedef vector<int> vi; 34 typedef vector<LL> vl; 35 typedef vector<vl> vvl; 36 typedef vector<bool> vb; 37 38 const int maxn = 25; 39 const LL mod = 2520; 40 LL dp[maxn][1<<8][mod]; 41 int digit[maxn]; 42 43 LL lcm(LL x, LL y) { 44 return x / __gcd(x, y) * y; 45 } 46 47 int get(int i, int s) { 48 if(i < 2) return s; 49 return s | (1 << (i-2)); 50 } 51 52 LL dfs(int l, int s, int sum, bool flag) { 53 if(l == 0) { 54 For(i, 2, 10) { 55 if(((1 << (i-2))& s) && (sum % i) != 0) return 0; 56 } 57 return 1; 58 } 59 if(!flag && ~dp[l][s][sum]) return dp[l][s][sum]; 60 LL ret = 0; 61 int pos = !flag ? 9 : digit[l]; 62 Rep(i, pos+1) { 63 ret += dfs(l-1, get(i, s), (sum*10+i)%mod, flag&&(i==pos)); 64 } 65 if(!flag) dp[l][s][sum] = ret; 66 return ret; 67 } 68 69 LL l, r; 70 71 LL f(LL x) { 72 int pos = 0; 73 while(x) { 74 digit[++pos] = x % 10; 75 x /= 10; 76 } 77 return dfs(pos, 0, 0, true); 78 } 79 80 signed main() { 81 //FRead(); 82 Clr(dp, -1); 83 int T; 84 Rint(T); 85 W(T) { 86 cin >> l >> r; 87 cout << f(r) - f(l-1) << endl; 88 } 89 RT 0; 90 }
One more time!
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 22; 6 const int mod = 2520; 7 LL l, r; 8 LL dp[maxn][1<<8][mod]; 9 int digit[maxn]; 10 11 int get(int i, int st) { 12 if(i < 2) return st; 13 return st | (1 << (i - 2)); 14 } 15 16 LL dfs(int l, int st, int sum, bool flag) { 17 if(l == 0) { 18 for(int i = 0; i <= 7; i++) { 19 if(st & (1 << i) && sum % (i + 2) != 0) return 0; 20 } 21 return 1; 22 } 23 if(!flag && ~dp[l][st][sum]) return dp[l][st][sum]; 24 int pos = flag ? digit[l] : 9; 25 LL ret = 0; 26 for(int i = 0; i <= pos; i++) { 27 ret += dfs(l-1, get(i, st), (sum*10+i)%mod, flag&&(i==pos)); 28 } 29 if(!flag) dp[l][st][sum] = ret; 30 return ret; 31 } 32 33 LL f(LL x) { 34 int pos = 0; 35 while(x) { 36 digit[++pos] = x % 10; 37 x /= 10; 38 } 39 return dfs(pos, 0, 0, true); 40 } 41 42 int main() { 43 // freopen("in", "r", stdin); 44 int T; 45 scanf("%d", &T); 46 memset(dp, -1, sizeof(dp)); 47 while(T--) { 48 scanf("%lld%lld",&l,&r); 49 printf("%lld ", f(r) - f(l-1)); 50 } 51 return 0; 52 }