BZOJ3679: 数字之积(数位dp)

题意

题目链接

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
*/