首页 > > 程序设计 > C/C++ >

BZOJ3679: 数字之积(数位dp)

2018-09-10 00:58:16来源：博客园阅读 ()

题意

题目链接

Sol

推什么结论啊。

直接大力dp，$f[i][j]$表示第$i$位，乘积为$j$，第二维直接开map

能赢！

/*
 
*/
#include<iostream>
#include<cstdio>
#include<map>
#define LL long long
using namespace std;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
LL L, R, L1, R1;
map<LL, LL> f[20];    
LL s[21], num = 0;
LL dfs(LL x, bool lim, LL mul) {
    if(x < 0) return 0;
    if(x == 0) {
        if(mul == -1) mul = 0;
        return mul >= L1 && mul <= R1;
    }
    if((!lim) && (f[x].find(mul) != f[x].end())) return f[x][mul]; 
    LL ans = 0;
    for(int i = 0; i <= (lim ? s[x] : 9); i++) {
        if(mul == -1) {
            if(i == 0) ans += dfs(x - 1, lim && (i == s[x]), -1);
            else ans += dfs(x - 1, lim && (i == s[x]), i);
        } else ans += dfs(x - 1, lim && (i == s[x]), i * mul);
    }
    if(!lim) f[x][mul] = ans;
    return ans;
}
LL solve(LL x) {
    if(x == -1) return 0;
    num = 0;
    while(x) s[++num] = x % 10, x /= 10;
    return dfs(num, 1, -1);
}
int main() {
    R1 = read();
    L = read(); R = read() - 1; L1 = 1;
    if(L == R + 1) {
        printf("%lld", L > 0 && L <= R1); return 0;
    }
    LL ans = solve(R) - solve(L - 1);
    cout << ans;
    return 0;
}
/*
23333
123456789 123456789123456789

6000000
123456 12345678

6
100 113

6
0 3
*/