Codeforces 1073E. Segment Sum (Digit DP)

日付: 11月 20, 2018

[Problem - 1073E - Codeforces](https://codeforces.com/problemset/problem/1073/E)
## Problem
Calculate the **sum** of numbers in range $[l,r]$ such that each number contains at most $k$ different digits.

**Constraints**: $1\le l \le r \le 10^{18},1\le k \le10$

## Solution
Apparently this is a typical digit dp problem, it is trivial to calculate the **count** of numbers that satisfies above condition. However, the task is to calculate the **sum**.

Let $C(p,mask)$ and $S(p,mask)$ be the count and sum of numbers with prefix before $p$-th digit contains different digits denoted by $mask$. At this moment the sum only consider suffix starting from $p$. If we choose some digit $i$ at position $p$, the sum will add two parts, one is remaining suffix starting from $p+1$ after $i$ is chosen, the other is the digit $i$ itself, whose contribution can be calculated by its value multiplies the number of times it appears.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)
#define FD(i,b,a) for(int i=(b);i>=(a);--i)
#define DEBUG(x) cerr << #x << ": " << (x) << endl;
constexpr LL inv(LL x, LL m) { return x > m ? inv(x % m, m) : x > 1 ? inv(m % x, m) * (m - m / x) % m : x; }
constexpr LL mpow(LL a, LL k, LL m) { LL r(1); for (a %= m; k; k >>= 1, a = a * a % m) if (k & 1)r = r * a % m; return r; }

int main() {
    LL l, r;
    int k;
    cin >> l >> r >> k;
    const int Mod = 998244353;
    int F[20][1030], G[20][1030];
    memset(F, -1, sizeof F);
    memset(G, -1, sizeof G);
    auto solve = [&](LL num) {
        string s = to_string(num);
        reverse(s.begin(), s.end());
        auto dp = [&](int p, int mask, bool head, bool limit, auto f) -> PII {
            if (p < 0) return {int(__builtin_popcount(mask) <= k), 0};
            if (!head && !limit && F[p][mask] != -1) return {F[p][mask], G[p][mask]};
            int cnt = 0, sum = 0, base = mpow(10, p, Mod);
            for (int i = 0; i <= (limit ? s[p] - '0' : 9); i++) {
                int nmask = mask;
                if (!(head && !i)) nmask |= 1 << i;
                int ncnt, nsum;
                tie(ncnt, nsum) = f(p - 1, nmask, head && !i, limit && i == s[p] - '0', f);
                cnt = (cnt + ncnt) % Mod;
                sum = (sum + nsum + 1LL * i * base * ncnt % Mod) % Mod;
            }
            if (!head && !limit) F[p][mask] = cnt, G[p][mask] = sum;
            return {cnt, sum};
        };
        return dp(s.length() - 1, 0, true, true, dp).second;
    };
    printf("%d\n", (solve(r) - solve(l - 1) + Mod) % Mod);
}
```

KONGROOの基地

このブログを検索

Codeforces 1073E. Segment Sum (Digit DP)

コメント

コメントを投稿