数位dp

2023-10-04 | 阅读：次

===

Index

力扣周赛题目
其它题目

力扣周赛题目

相邻数位差的绝对值恰好为1的数

周赛356 T4

给你两个正整数 low 和 high ，都用字符串表示，请你统计闭区间 [low, high] 内的步进数字数目。如果一个整数相邻数位之间差的绝对值都恰好是 1 ，那么这个数字被称为步进数字。

请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。

由于答案可能很大，请你将它对 109 + 7 取余后返回。

注意 步进数字不能有前导 0

1 <= int(low) <= int(high) <= 1e100
low, high 不包含前导0，且只包含数字字符

分析

dfs(p, pre, limit, is_num) 表示当前第p位(从高到低)，上一位填的pre的步进数字数目。

limit: 是否收到n的约束，limit为true时up只能取到s[p],否则 up可以取到9.
is_num: 是否已经填了数字，is_num为0时可以选择跳过或者当前填1-up，is_num为1时可以填0-up。

const int M = 1000000007;
using T = int;
T dp(string &s) {
    int n = s.size();
    vector f(n, vector<T>(10, -1));
    function<T(int, int, bool, bool)> dfs = [&](int p, int pre, bool limit, bool is_num) -> T {
        if (p == n) return is_num; // is_num 为 true 表示得到了一个合法数字
        if (!limit && is_num && ~f[p][pre]) return f[p][pre];
        T res{};
        if (!is_num) res = dfs(p + 1, pre, false, false);
        int up = limit ? s[p] - '0' : 9;
        for (int i = 1 - is_num; i <= up; ++i) {
            if (!is_num || abs(i - pre) == 1) 
                res = (res + dfs(p + 1, i, limit && i == up, true)) % M;
        }
        if (!limit && is_num) f[p][pre] = res;
        return res;
    };
    return dfs(0, 0, true, false);
}

class Solution {
public:
    int countSteppingNumbers(string low, string high) {
        auto is_valid = [&](string &s) {
            for (int i = 1; i < s.size(); ++i) 
                if (abs(s[i] - s[i - 1]) != 1) return false;
            return true;
        };
        return (dp(high) - dp(low) + M + is_valid(low)) % M;
    }
};

整除k且奇偶数位数目相同的数

双周赛111 T4

给你正整数 low ，high 和 k 。

如果一个数满足以下两个条件，那么它是美丽的：

偶数数位的数目与奇数数位的数目相同。
这个整数可以被 k 整除。请你返回范围 [low, high] 中美丽整数的数目。
0 < low <= high <= 1e9
0 < k <= 20

分析

dfs(p, v, d, limit, is_num) 表示构造第p位及之后的合法方案数。其中

v : 已经构造的数位模k等于v
d : 表示已经构造的数位中奇数数位的数目与偶数数位的数目的差，在递归终点，判断是否满足 d == 0，注意我们无需对奇数数位的数目和偶数数位的数目分别各用一个参数表示，那样效率更低。假设填入的数字是 i 那么将 d += (i & 1 : 1 : -1)，对应着奇数加一，偶数减一。由于可能出现负数下标，这里对d加上n偏移量。

// Ndarray
using T = int;
T dp(string &s, int k) {
    int n = s.size();
    ndarr<T, 3> f({n, k, n * 2 + 1}, -1);
    function<T(int, int, int, bool, bool)> dfs = [&](int p, int v, int d, bool limit, bool is_num) -> T {
        if (p == n) return is_num && !v && d == n; // 模为0，且奇偶数位相同(偏移量n)
        if (!limit && is_num && ~f[{p, v, d}]) return f[{p, v, d}];
        T res{};
        if (!is_num) res = dfs(p + 1, v, d, false, false);
        int up = limit ? s[p] - '0' : 9;
        for (int i = 1 - is_num; i <= up; ++i) {
            res += dfs(p + 1, (v * 10 + i) % k, d + (i % 2 == 1 ? 1 : -1), limit && i == up, true);
        }
        if (!limit && is_num)
            f[{p, v, d}] = res;
        return res;
    };
    return dfs(0, 0, n, true, false);
}

class Solution {
public:
    int numberOfBeautifulIntegers(int low, int high, int k) {
        string r = to_string(high), l = to_string(low - 1);
        int x = dp(r, k), y = dp(l, k);
        return x - y;
    }
};

数字1出现的个数

lc233

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

0 <= n <= 1e9

分析

dfs(p, cnt, limit, is_num) 表示从高位到低位当前第p位，已经出现cnt个1，继续构造最终会得到的1的个数。

using T = int;
T dp(string s) {
    int n = s.size();
    vector f(n, vector<T>(n, -1));
    function<T(int, int, bool, bool)> dfs = [&](int p, int cnt, bool limit, bool is_num) -> T {
        if (p == n) return cnt; 
        if (!limit && is_num && ~f[p][cnt]) return f[p][cnt];
        T res{};
        if (!is_num) res = dfs(p + 1, cnt, false, false);
        int up = limit ? s[p] - '0' : 9;
        for (int i = 1 - is_num; i <= up; ++i) {
            res += dfs(p + 1, cnt + (i == 1), limit && i == up, true);
        }
        if (!limit && is_num)
            f[p][cnt] = res;
        return res;
    };
    return dfs(0, 0, true, false);
}
class Solution {
public:
    int countDigitOne(int n) {
        string s = to_string(n);
        return dp(s);
    }
};

旋转数字数目

lc788

定义一个数x位好数，如果x每一位旋转后仍是一个有效数字，且和 x不同。给定正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

其中 0, 1, 8 旋转后为自身，(2,5), (6,9)互相旋转为对方，3，4，7 旋转后为无效数字。

1 <= n <= 1e9

分析

好数有两个性质，1. 不包含3,4,7, 2. 至少包含一个2,5,6,9中的数字。

dfs(p, has_diff, limit) 表示当前第p位，has_diff表示当前构造的数中是否存在2,5,6,9。

using T = int;
T dp(string &s) {
    int n = s.size();
    vector f(n, vector<T>(2, -1));
    int st[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
    function<T(int,bool, bool)> dfs = [&](int p, bool has_diff, bool limit) -> T {
        if (p == n) return has_diff; 
        if (!limit && ~f[p][has_diff]) return f[p][has_diff];
        T res{};
        int up = limit ? s[p] - '0' : 9;
        for (int i = 0; i <= up; ++i) {
            if (~st[i]) {
                res += dfs(p + 1, has_diff | st[i], limit && i == up);
            }
        }
        if (!limit)
            f[p][has_diff] = res;
        return res;
    };
    return dfs(0, false, true);
}

class Solution {
public:
    int rotatedDigits(int n) {
        string s = to_string(n);
        return dp(s);
    }
};

至少有1位重复的数字

周赛306t4

同 lc2376

给定正整数 n，返回在 [1, n] 范围内具有至少 1 位重复数字的正整数的个数。

1 <= n <= 1e9

分析

反过来求每一位数都互不相同的数。

dfs(p, mask, limit, is_num) 当前第p位，所选数字组成集合位mask的方案数。

using T = int;
T dp(string s) {
    int n = s.size();
    vector f(n, vector<T>(1 << 10, -1));
    function<T(int, int, bool, bool)> dfs = [&](int p, int mask, bool limit, bool is_num) -> T {
        if (p == n) return is_num; 
        if (!limit && is_num && ~f[p][mask]) return f[p][mask];
        T res{};
        if (!is_num) res = dfs(p + 1, mask, false, false);
        int up = limit ? s[p] - '0' : 9;
        for (int i = 1 - is_num; i <= up; ++i) {
            if (!((mask >> i) & 1))
                res += dfs(p + 1, mask | (1 << i), limit && i == up, true);
        }
        if (!limit && is_num)
            f[p][mask] = res;
        return res;
    };
    return dfs(0, 0, true, false);
}
class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        string s = to_string(n);
        return n - dp(s);
    }
};

二进制表示不含连续1的数字

lc600

给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在连续的 1 。

1 <= n <= 1e9

分析

本题统计二进制表示中的数字，所以需要将n转化为二进制表示，在二进制下进行统计，其中 up 上限为1，由于前导0不会影响最终结果，这里将is_num参数删除。

using T = int;
T dp(string s) {
    int n = s.size();
    vector f(n, vector<T>(2, -1));
    function<T(int, int, bool)> dfs = [&](int p, int pre, bool limit) -> T {
        if (p == n) return 1; 
        if (!limit && ~f[p][pre]) return f[p][pre];
        T res{};
        int up = limit ? s[p] - '0' : 1;  // 二进制上限为1
        for (int i = 0; i <= up; ++i) {
            if (!(pre && i == 1))
                res += dfs(p + 1, i, limit && i == up);
        }
        if (!limit)
            f[p][pre] = res;
        return res;
    };
    return dfs(0, 0, true);
}

class Solution {
public:
    int findIntegers(int n) {
        string s = bitset<30>(n).to_string(); // 转化为二进制
        return dp(s);
    }
};

数位和在某个区间内的数字

周赛348 T4

给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：

num1 <= x <= num2
min_sum <= digit_sum(x) <= max_sum. 请你返回好整数的数目。答案可能很大，请返回答案对 109 + 7 取余后的结果。
1 <= num1 <= num2 <= 1e22
1 <= min_sum <= max_sum <= 400

分析

dfs(p, sum, limit) 当前第p位，已经填的数位和为sum，继续构造到最后的方案数。

const int M = 1000000007;
using T = int;
T dp(string &s, int mn_sum, int mx_sum) {
    int n = s.size();
    vector f(n, vector<T>(mx_sum + 1, -1));
    function<T(int, int, bool)> dfs = [&](int p, int sum, bool limit) -> T {
        if (sum > mx_sum) return 0; // 剪枝
        if (p == n) return sum >= mn_sum; 
        if (!limit && ~f[p][sum]) return f[p][sum];
        T res{};
        int up = limit ? s[p] - '0' : 9;
        for (int i = 0; i <= up; ++i) {
            res = (res + dfs(p + 1, sum + i,  limit && i == up)) % M;
        }
        if (!limit)
            f[p][sum] = res;
        return res;
    };
    return dfs(0, 0, true);
}

class Solution {
public:
    int count(string s1, string s2, int min_sum, int max_sum) {
        auto chk = [&](string &s) {
            int sum = 0;
            for (auto &c : s) 
                sum += c - '0';
            return sum >= min_sum && sum <= max_sum;
        };
        return (dp(s2, min_sum, max_sum) - dp(s1, min_sum, max_sum) + M + chk(s1)) % M;
    }
};

其它题目

无相邻重复数字的数

cses 2220

求区间[a,b]中有多少个数字x满足：x的十进制表示中无相邻重复数字。

0 <= a <= b <= 1e18

using T = long long;
T dp(string s) {
    int n = s.size();
    vector f(n, vector<T>(10, -1));
    function<T(int, int, bool, bool)> dfs = [&](int p, int pre, bool limit, bool is_num) -> T {
        if (p == n) return is_num; 
        if (!limit && is_num && ~f[p][pre]) return f[p][pre];
        T res{};
        if (!is_num) res = dfs(p + 1, pre, false, false);
        int up = limit ? s[p] - '0' : 9;
        for (int i = 1 - is_num; i <= up; ++i) {
            if (pre != i)
                res += dfs(p + 1, i, limit && i == up, true);
        }
        if (!limit && is_num)
            f[p][pre] = res;
        return res;
    };
    return dfs(0, 0, true, false);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    string a, b;
    cin >> a >> b;

    auto chk = [&](string &s) {
        for (int i = 1; i < s.size(); ++i) if (s[i] == s[i - 1]) 
            return 0;
        return 1;
    };

    cout << dp(b) - dp(a) + chk(a) << '\n';

    return 0;
}

不降数

牛客-不降数

求区间[a,b]中有多少个数字x满足：x的十进制表示从左到右各位数字呈非下降关系。

0 <= a <= b <= 2^31

using T = int;
T dp(string s) {
    int n = s.size();
    vector f(n, vector<T>(10, -1));
    function<T(int, int, bool, bool)> dfs = [&](int p, int pre, bool limit, bool is_num) -> T {
        if (p == n) return is_num; 
        if (!limit && is_num && ~f[p][pre]) return f[p][pre];
        T res{};
        if (!is_num) res = dfs(p + 1, pre, false, false);
        int up = limit ? s[p] - '0' : 9;
        for (int i = max(1 - is_num, pre); i <= up; ++i) {
            res += dfs(p + 1, i, limit && i == up, true);
        }
        if (!limit && is_num)
            f[p][pre] = res;
        return res;
    };
    return dfs(0, 0, true, false);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int a, b;
    while (cin >> a >> b){
        string s = to_string(b), t = to_string(a - 1);;
        cout << dp(s) - dp(t) << '\n';
    }
    return 0;
}

相邻数字之差的绝对值至少为2

luogup2657 windy数

求区间[a,b]中有多少个正整数x满足：x不含前导零且相邻两个数字之差至少为2。

1 <= a <= b <= 2e9

using T = int;
T dp(string s) {
    int n = s.size();
    vector f(n, vector<T>(10, -1));
    function<T(int, int, bool, bool)> dfs = [&](int p, int pre, bool limit, bool is_num) -> T {
        if (p == n) return is_num; 
        if (!limit && is_num && ~f[p][pre]) return f[p][pre];
        T res{};
        if (!is_num) res = dfs(p + 1, pre, false, false);
        int up = limit ? s[p] - '0' : 9;
        for (int i = 1 - is_num; i <= up; ++i) {
            if (abs(i - pre) >= 2)
                res += dfs(p + 1, i, limit && i == up, true);
        }
        if (!limit && is_num)
            f[p][pre] = res;
        return res;
    };
    return dfs(0, -2, true, false);  // 注意 pre 不能初始化为0，否则第1位为1时不满足abs(i - pre) >= 2
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int a, b;
    cin >> a >> b;

    string s = to_string(b), t = to_string(a - 1);
    cout << dp(s) - dp(t) << '\n';

    return 0;
}

每个数字的出现次数

spoj 3928

给定两个整数 a 和 b 我们在列表中写出 [a,b] 之间的数字。您的任务是计算每个数字的出现次数。

1 <= a, b <= 1e8

分析

使用 数字1出现的个数 的代码，对[0,9]都统计一遍即可。

using T = int;
T dp(string &s, int k) {
    int n = s.size();
    vector<vector<T>> f(n, vector<T>(n, -1));
    function<T(int, int, bool, bool)> dfs = [&](int p, int cnt, bool limit, bool is_num) -> T {
        if (p == n) return cnt; 
        if (!limit && is_num && ~f[p][cnt]) return f[p][cnt];
        T res{};
        if (!is_num) res = dfs(p + 1, cnt, false, false);
        int up = limit ? s[p] - '0' : 9;
        for (int i = 1 - is_num; i <= up; ++i) {
            res += dfs(p + 1, cnt + (i == k), limit && i == up, true);
        }
        if (!limit && is_num)
            f[p][cnt] = res;
        return res;
    };
    return dfs(0, 0, true, false);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int a, b;
    while (cin >> a >> b && (a || b)) {
        if (a > b) swap(a, b); // a 可能大于b
        string s = to_string(b), t = to_string(a - 1);

        for (int i = 0; i < 10; ++i) 
            cout << dp(s, i) - dp(t, i) << " \n"[i == 9];
    }
    return 0;
}

平衡数字

spoj balances number

一个数被称为是平衡的数，当且仅当对于所有出现过的数位（即 0−9 ），每个偶数出现奇数次，每个奇数出现偶数次。给定 [A,B],求[A,B]内所有平衡数的个数。

1 <= A <= B <= 1e19

分析

dp[p][st][mask]: 当前第p个元素，0-9是否出现用st表示，0-9出现的奇偶性用mask表示。

using T = unsigned long long;
const int N = 20;
T f[N][1 << 10][1 << 10];
T dp(string &s) {
    int n = s.size();
    function<T(int, int, int, bool, bool)> dfs = [&](int p, int st, int mask, bool limit, bool is_num) -> T {
        if (p == n) {
            bool o = 1;
            for (int i = 0; i < 10; ++i) {
                if ((st >> i & 1) && (mask >> i & 1) == (i & 1)) o = 0;
            }
            return is_num && o;
        }
        if (!limit && is_num && ~f[p][st][mask]) return f[p][st][mask];
        T res{};
        if (!is_num) res = dfs(p + 1, st, mask, false, false);
        int up = limit ? s[p] - '0' : 9;
        for (int i = 1 - is_num; i <= up; ++i) {
            res += dfs(p + 1, st | (1 << i), mask ^ (1 << i), limit && i == up, true);
        }
        if (!limit && is_num)
            f[p][st][mask] = res;
        return res;
    };
    return dfs(0, 0, 0, true, false);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    T a, b;
    int t;
    cin >> t;
    while (t--) {
        cin >> a >> b;
        string s = to_string(b), t = to_string(a - 1);
        memset(f, -1, sizeof(f));  // 每次dp前都需要memset，不然会wa
        auto x = dp(s);
        memset(f, -1, sizeof(f));
        auto y = dp(t);
        cout << x - y << '\n';
    }
    return 0;
}

被数位和整除的数字

atcoder abc336e

求1-n中有多少个数能被其数位和整除。

1 <= n <= 1e14

分析

枚举所有可能数位和，对于数位和k，求解如下问题： 1-n中有多少个数数位和为k，且原数整除k。

using T = ll;
T dp(string &s, int k) {
    int n = s.size();
    ndarr<T, 3> f({n, n*10+4, k}, -1);
    function<T(int, int, int, bool, bool)> dfs = [&](int p, int sum, int d, bool limit, bool is_num) -> T {
        if (p == n) return is_num && sum == k && !d; // 模为0，且奇偶数位相同(偏移量n)
        if (!limit && is_num && ~f[{p, sum, d}]) return f[{p, sum, d}];
        T res{};
        if (!is_num) res = dfs(p + 1, sum, d, false, false);
        int up = limit ? s[p] - '0' : 9;
        for (int i = 1 - is_num; i <= up; ++i) {
            if (sum + i <= k)
                res += dfs(p + 1, sum + i, (d * 10 + i) % k, limit && i == up, true);
        }
        if (!limit && is_num)
            f[{p, sum, d}] = res;
        return res;
    };
    return dfs(0, 0, 0, true, false);
}
void ac_yyf(int tt) {
    string s;
    cin>>s;
    ll ans=0;
    for(int i=1;i<=9*sz(s);++i){
        ans+=dp(s,i);
    }
    cout<<ans<<nl;
}