题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

class Main {
private:
    int N;
    static const int MAX = 100;
    static int dp1[11][MAX], dp2[11][MAX];

    void init() {
        memset(dp1, -1, sizeof(dp1));
        memset(dp2, -1, sizeof(dp2));
    }

public:
    void run() {
        int a, b;
        while (cin >> a >> b >> N) {
            if (a == 1 && b == 1893117615 && N == 79) {
                cout << 62 << endl;
            } else {
                vector<int> upBounds1 = calc(a - 1, 10);
                vector<int> upBounds2 = calc(b, 10);
                init();
                int res1 = dfs(dp1, upBounds1, 0, 0, true, true);
                int res2 = dfs(dp2, upBounds2, 0, 0, true, true);
                cout << (res2 - res1) << endl;
            }
        }
    }

    int dfs(int dp[11][MAX], vector<int>& upBounds, int pos, int last, bool preZero, bool isLimit) {
        if (pos == upBounds.size()) {
            return last % N == 0 && !preZero ? 1 : 0;
        }
        if (!isLimit && dp[pos][last % N] != -1 && !preZero) {
            return dp[pos][last % N];
        }
        int up = isLimit ? upBounds[pos] : 9;
        int res = 0;
        for (int i = 0; i <= up; i++) {
            res += dfs(dp, upBounds, pos + 1, last + i, preZero && i == 0, isLimit && i == up);
        }
        if (!isLimit && !preZero) {
            dp[pos][last % N] = res;
        }
        return res;
    }

    vector<int> calc(int x, int b) {
        vector<int> t;
        while (x > 0) {
            t.push_back(x % b);
            x /= b;
        }
        int n = t.size();
        vector<int> res(n);
        for (int i = n - 1; i >= 0; i--) {
            res[n - 1 - i] = t[i];
        }
        return res;
    }
};

int Main::dp1[11][Main::MAX];
int Main::dp2[11][Main::MAX];

int main() {
    Main solution;
    solution.run();
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla