Digit DP - Advanced States

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count numbers in [0, N] such that
5
//   (sum of digits) % m == a  AND  number % k == b
6
// Classic multi-constraint Digit DP with states: pos, sumMod, rem, started, tight
7
8
struct SumRemainderDP {
9
    vector<int> digs;     // digits of N from most significant to least
10
    int m, a, k, b;
11
12
    // dp[pos][sumMod][rem][started][tight] => -1 means uncomputed
13
    vector<vector<vector<array<array<long long,2>,2>>>> dp;
14
15
    long long dfs(int pos, int sumMod, int rem, int started, int tight) {
16
        if (pos == (int)digs.size()) {
17
            // Terminal condition: check constraints
18
            // If started==0, the number is 0 (all leading zeros). Its sum is 0 and remainder is 0.
19
            int finalSum = sumMod;
20
            int finalRem = rem;
21
            // Note: when started==0, sumMod and rem are both 0 from initialization.
22
            return (finalSum % m == a % m) && (finalRem % k == b % k) ? 1LL : 0LL;
23
        }
24
        long long &memo = dp[pos][sumMod][rem][started][tight];
25
        if (memo != -1) return memo;
26
        long long ans = 0;
27
        int up = tight ? digs[pos] : 9;
28
        for (int d = 0; d <= up; ++d) {
29
            int ntight = tight && (d == up);
30
            int nstarted = started || (d != 0);
31
            int nsum = sumMod;
32
            int nrem = rem;
33
            if (nstarted) {
34
                nsum = (sumMod + d) % m;
35
                nrem = ( (rem * 10) + d ) % k;
36
            } else {
37
                // still leading zeros: keep sum=0 and rem=0
38
                nsum = 0;
39
                nrem = 0;
40
            }
41
            ans += dfs(pos + 1, nsum, nrem, nstarted, ntight);
42
        }
43
        memo = ans;
44
        return ans;
45
    }
46
47
    long long solve(long long N, int m_, int a_, int k_, int b_) {
48
        m = m_; a = ((a_%m)+m)%m; k = k_; b = ((b_%k)+k)%k;
49
        if (N < 0) return 0; // empty set
50
        // Extract digits
51
        digs.clear();
52
        {
53
            if (N == 0) digs = {0};
54
            else {
55
                vector<int> tmp;
56
                while (N > 0) { tmp.push_back((int)(N % 10)); N /= 10; }
57
                reverse(tmp.begin(), tmp.end());
58
                digs = tmp;
59
            }
60
        }
61
        // Initialize DP with -1
62
        dp.assign(digs.size(), {});
63
        dp.resize(digs.size(), vector<vector<array<array<long long,2>,2>>>(m, vector<array<array<long long,2>,2>>(k)));
64
        for (int i = 0; i < (int)digs.size(); ++i)
65
            for (int sm = 0; sm < m; ++sm)
66
                for (int r = 0; r < k; ++r)
67
                    for (int st = 0; st < 2; ++st)
68
                        for (int ti = 0; ti < 2; ++ti)
69
                            dp[i][sm][r][st][ti] = -1;
70
        return dfs(0, 0, 0, 0, 1);
71
    }
72
};
73
74
int main() {
75
    ios::sync_with_stdio(false);
76
    cin.tie(nullptr);
77
78
    long long L = 1, R = 1000000000000LL; // 1e12 example
79
    int m = 7, a = 3;                    // sum of digits ≡ 3 (mod 7)
80
    int k = 11, b = 7;                   // number ≡ 7 (mod 11)
81
82
    SumRemainderDP solver;
83
    long long ansR = solver.solve(R, m, a, k, b);
84
    long long ansL = solver.solve(L - 1, m, a, k, b);
85
    cout << (ansR - ansL) << "\n";
86
    return 0;
87
}
88

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count numbers in [0, N] that:
5
//  - contain a given digit pattern P at least once (as a substring), and
6
//  - have no two adjacent equal digits.
7
// Advanced state: KMP automaton state + seen flag + last digit + started + tight.
8
9
struct KMPDigitDP {
10
    vector<int> digs; // digits of N
11
    string P;         // pattern over digits '0'..'9'
12
    vector<int> pi;   // prefix function
13
    vector<array<int,10>> nxt; // automaton transitions for states 0..|P|
14
15
    // Build prefix function
16
    vector<int> build_pi(const string &s) {
17
        int n = (int)s.size();
18
        vector<int> p(n, 0);
19
        for (int i = 1; i < n; ++i) {
20
            int j = p[i-1];
21
            while (j > 0 && s[i] != s[j]) j = p[j-1];
22
            if (s[i] == s[j]) ++j;
23
            p[i] = j;
24
        }
25
        return p;
26
    }
27
28
    void build_automaton() {
29
        int A = (int)P.size();
30
        pi = build_pi(P);
31
        nxt.assign(A + 1, {});
32
        for (int s = 0; s <= A; ++s) {
33
            for (int d = 0; d < 10; ++d) {
34
                char c = char('0' + d);
35
                int j = s;
36
                // Move using KMP failure links
37
                while (j > 0 && (j == A || P[j] != c)) j = pi[j-1];
38
                if (j < A && P[j] == c) ++j;
39
                // j in [0..A]; if j==A, we matched the pattern just now
40
                nxt[s][d] = j;
41
            }
42
        }
43
    }
44
45
    // We'll memoize using a hash map with packed key to keep code compact.
46
    unordered_map<unsigned long long, long long> memo;
47
48
    // Pack state into 64 bits: pos(6) | kmp(6) | last(4) | seen(1) | started(1) | tight(1)
49
    // pos up to 19 -> 5 bits ok; use 6 for safety. kmp up to |P| (<= 50 typical) -> 6-8 bits ok.
50
    unsigned long long pack(int pos, int kmp, int last, int seen, int started, int tight) {
51
        unsigned long long key = 0;
52
        key |= (unsigned long long)pos;
53
        key |= (unsigned long long)kmp << 6;
54
        key |= (unsigned long long)last << 12;
55
        key |= (unsigned long long)seen << 16;
56
        key |= (unsigned long long)started << 17;
57
        key |= (unsigned long long)tight << 18;
58
        return key;
59
    }
60
61
    long long dfs(int pos, int kmp, int last, int seen, int started, int tight) {
62
        if (pos == (int)digs.size()) {
63
            return seen ? 1LL : 0LL;
64
        }
65
        auto key = pack(pos, kmp, last, seen, started, tight);
66
        auto it = memo.find(key);
67
        if (it != memo.end()) return it->second;
68
        long long ans = 0;
69
        int up = tight ? digs[pos] : 9;
70
        for (int d = 0; d <= up; ++d) {
71
            int ntight = tight && (d == up);
72
            int nstarted = started || (d != 0);
73
            int nlast = last;
74
            int nkmp = kmp;
75
            int nseen = seen;
76
77
            if (!nstarted) {
78
                // still leading zeros: do not update last or automaton
79
                nlast = 10; // sentinel for 'no last digit'
80
                nkmp = 0;
81
            } else {
82
                // no adjacent equal digits constraint
83
                if (last != 10 && d == last) continue;
84
                // KMP automaton transition on digit d
85
                int j = nxt[kmp][d];
86
                if (j == (int)P.size()) {
87
                    nseen = 1;
88
                    // Continue from border state after a match
89
                    j = (P.size() > 0 ? pi[P.size()-1] : 0);
90
                }
91
                nkmp = j;
92
                nlast = d;
93
            }
94
            ans += dfs(pos + 1, nkmp, nlast, nseen, nstarted, ntight);
95
        }
96
        memo[key] = ans;
97
        return ans;
98
    }
99
100
    long long solve(long long N, const string &pattern) {
101
        if (N < 0) return 0;
102
        P = pattern;
103
        build_automaton();
104
        // Extract digits of N
105
        digs.clear();
106
        if (N == 0) digs = {0};
107
        else {
108
            vector<int> tmp;
109
            while (N > 0) { tmp.push_back((int)(N % 10)); N /= 10; }
110
            reverse(tmp.begin(), tmp.end());
111
            digs = tmp;
112
        }
113
        memo.clear();
114
        return dfs(0, 0, 10, 0, 0, 1);
115
    }
116
};
117
118
int main() {
119
    ios::sync_with_stdio(false);
120
    cin.tie(nullptr);
121
122
    long long L = 1, R = 1000000; // up to 1e6 for demo
123
    string pattern = "13";       // require substring "13"
124
125
    KMPDigitDP solver;
126
    long long ansR = solver.solve(R, pattern);
127
    long long ansL = solver.solve(L - 1, pattern);
128
    cout << (ansR - ansL) << "\n";
129
    return 0;
130
}
131

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count numbers in [0, N] such that
5
//   (product of digits) % m == p  AND  (count of digit 0) <= c
6
// States: pos, prodMod, zeroCount (capped), started, tight
7
8
struct ProductZeroCapDP {
9
    vector<int> digs;
10
    int m, p, c;
11
    // dp[pos][prod][z][started][tight]
12
    vector<vector<vector<array<array<long long,2>,2>>>> dp;
13
14
    long long dfs(int pos, int prod, int z, int started, int tight) {
15
        if (pos == (int)digs.size()) {
16
            // Special handling for the number 0 (started==0): interpret as single digit 0
17
            int finalProd = prod;
18
            int finalZ = z;
19
            if (!started) { finalProd = 0 % m; finalZ = 1; }
20
            return (finalProd % m == p % m) && (finalZ <= c) ? 1LL : 0LL;
21
        }
22
        long long &memo = dp[pos][prod][z][started][tight];
23
        if (memo != -1) return memo;
24
        long long ans = 0;
25
        int up = tight ? digs[pos] : 9;
26
        for (int d = 0; d <= up; ++d) {
27
            int ntight = tight && (d == up);
28
            int nstarted = started || (d != 0);
29
            int nprod = prod;
30
            int nz = z;
31
            if (!nstarted) {
32
                // still leading: neutral product 1, zero count 0
33
                nprod = 1 % m;
34
                nz = 0;
35
            } else {
36
                if (d == 0) {
37
                    nprod = 0; // once zero appears, product is 0 modulo m
38
                    if (nz < c) nz = nz + 1; else { // prune if exceeding cap
39
                        // even though we'll check at the end, pruning early saves work
40
                        // but be careful not to skip other digits at this position
41
                    }
42
                } else {
43
                    nprod = (int)((1LL * prod * d) % m);
44
                }
45
            }
46
            if (nz <= c) ans += dfs(pos + 1, nprod, nz, nstarted, ntight);
47
        }
48
        memo = ans;
49
        return ans;
50
    }
51
52
    long long solve(long long N, int m_, int p_, int c_) {
53
        if (N < 0) return 0;
54
        m = m_; p = ((p_%m)+m)%m; c = c_;
55
        // Extract digits
56
        digs.clear();
57
        if (N == 0) digs = {0};
58
        else {
59
            vector<int> tmp;
60
            while (N > 0) { tmp.push_back((int)(N % 10)); N /= 10; }
61
            reverse(tmp.begin(), tmp.end());
62
            digs = tmp;
63
        }
64
        // Initialize DP: prod in [0..m-1], z in [0..c]
65
        dp.assign(digs.size(), vector<vector<array<array<long long,2>,2>>>(m, vector<array<array<long long,2>,2>>(c + 1)));
66
        for (int i = 0; i < (int)digs.size(); ++i)
67
            for (int pr = 0; pr < m; ++pr)
68
                for (int z = 0; z <= c; ++z)
69
                    for (int st = 0; st < 2; ++st)
70
                        for (int ti = 0; ti < 2; ++ti)
71
                            dp[i][pr][z][st][ti] = -1;
72
        // Start with neutral product=1 (mod m), zero count=0, not started, tight=1
73
        return dfs(0, 1 % m, 0, 0, 1);
74
    }
75
};
76
77
int main() {
78
    ios::sync_with_stdio(false);
79
    cin.tie(nullptr);
80
81
    long long L = 1, R = 5000000; // demo range
82
    int m = 9, p = 0;             // product of digits ≡ 0 (mod 9)
83
    int c = 2;                    // at most two zeros allowed
84
85
    ProductZeroCapDP solver;
86
    long long ansR = solver.solve(R, m, p, c);
87
    long long ansL = solver.solve(L - 1, m, p, c);
88
    cout << (ansR - ansL) << "\n";
89
    return 0;
90
}
91

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count numbers in [0, N] where each digit appears an even number of times
5
// Uses an iterative DP with rolling arrays to demonstrate memory optimization.
6
// State: position, mask(10 bits parity), started, tight.
7
8
long long solve_even_parities(long long N) {
9
    if (N < 0) return 0;
10
    vector<int> digs;
11
    if (N == 0) digs = {0};
12
    else { vector<int> t; while (N) { t.push_back(N % 10); N /= 10; } reverse(t.begin(), t.end()); digs = t; }
13
    int D = (int)digs.size();
14
15
    // dp[tight][started][mask]
16
    const int MASKS = 1 << 10;
17
    vector<vector<long long>> cur(2, vector<long long>(MASKS*2, 0));
18
    vector<vector<long long>> nxt(2, vector<long long>(MASKS*2, 0));
19
    auto idx = [&](int started, int mask){ return started*MASKS + mask; };
20
21
    // Initialize at position 0
22
    cur[1][idx(0, 0)] = 1; // tight=1, started=0, mask=0
23
24
    for (int pos = 0; pos < D; ++pos) {
25
        // clear next
26
        for (int t = 0; t < 2; ++t) fill(nxt[t].begin(), nxt[t].end(), 0LL);
27
        for (int tight = 0; tight < 2; ++tight) {
28
            int up = tight ? digs[pos] : 9;
29
            for (int started = 0; started < 2; ++started) {
30
                for (int mask = 0; mask < MASKS; ++mask) {
31
                    long long ways = cur[tight][idx(started, mask)];
32
                    if (!ways) continue;
33
                    for (int d = 0; d <= up; ++d) {
34
                        int ntight = tight && (d == up);
35
                        int nstarted = started || (d != 0);
36
                        int nmask = mask;
37
                        if (nstarted) {
38
                            nmask ^= (1 << d); // toggle parity of digit d
39
                        }
40
                        nxt[ntight][idx(nstarted, nmask)] += ways;
41
                    }
42
                }
43
            }
44
        }
45
        swap(cur, nxt);
46
    }
47
48
    long long ans = 0;
49
    // Sum counts where mask==0 (all digits even). Include started=0 (the number 0) as even.
50
    for (int tight = 0; tight < 2; ++tight) {
51
        ans += cur[tight][idx(0, 0)];
52
        ans += cur[tight][idx(1, 0)];
53
    }
54
    return ans;
55
}
56
57
int main(){
58
    ios::sync_with_stdio(false);
59
    cin.tie(nullptr);
60
61
    long long L = 0, R = 1000000; // demo
62
    long long ans = solve_even_parities(R) - solve_even_parities(L - 1);
63
    cout << ans << "\n";
64
    return 0;
65
}
66