lc t4

class Solution {
    vector<vector<int>> dp;
    vector<int> digits;
    int dcnt;

    int search(int pos, int limit, int lz, int state) {
        if (pos == -1)  {
            if (lz) return state <= 1 ? 0 : 1;
            return state != 0;
        }
        int ub = (limit ? digits[pos] : 9);
        int ret = 0;
        if (pos == 1) printf("lz:%d, limit:%d ret:%d state:%d\n", lz, limit, ret, state);
        if (lz == 0 && limit == 0 && dp[pos][state] != -1) return dp[pos][state];

        for (int i = 0; i <= ub; ++i) {
            if (i == 0) {
                if (lz == 0) {
                    if ((state & 0x01) == 0) {
                        // int lz0 = search(pos - 1, 0, 0, state | 1); // wa
                        int lz0 = search(pos - 1, limit && i == ub, 0, state | 1); // ac
                        ret += lz0;
                        if (pos == 1)
                        printf("lz0:%d\n", lz0);
                    }
                } else {
                    int lz1 = search(pos - 1, 0, lz, state);
                    ret += lz1;
                    if (pos == 1)
                    printf("lz1:%d\n", lz1);
                }
            } else {
                if (((1 << i) & state) == 0) {
                    int li = search(pos - 1, limit && i == ub, 0, state | (1 << i));
                    if (pos == 1) {
                        printf("li:%d\n", li);
                    }
                    ret += li;
                }
            }
        }

        // if (state == (1 << 4) + (1 << 0)) {
        if (pos == 1) {
            printf("limit:%d lz:%d ret:%d st:%d pos:%d\n", limit, lz, ret, state, pos);
        }
        if (lz == 0 && limit == 0) dp[pos][state] = ret;
        return ret;
    }
public:
    int countSpecialNumbers(int n) {
        dp = vector<vector<int>>(1<<4, vector<int>(1 << 10, -1));
        int nn = n;
        dcnt = 0;
        digits = vector<int>(16);
        while(nn != 0) { digits[dcnt++] = nn % 10; nn /= 10; }
        int ans = search(dcnt - 1, 1, 1, 0);
        return ans;
    }
};