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 <math><semantics><mrow><mo>[</mo><mi>l</mi><mo separator="true">,</mo><mi>r</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[l,r]</annotation></semantics></math>[l,r] such that each number contains at most <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k different digits.

**Constraints**: <math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>l</mi><mo>≤</mo><mi>r</mi><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>18</mn></msup><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mn>10</mn></mrow><annotation encoding="application/x-tex">1\le l \le r \le 10^{18},1\le k \le10</annotation></semantics></math>1≤l≤r≤1018,1≤k≤10

## 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 <math><semantics><mrow><mi>C</mi><mo>(</mo><mi>p</mi><mo separator="true">,</mo><mi>m</mi><mi>a</mi><mi>s</mi><mi>k</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">C(p,mask)</annotation></semantics></math>C(p,mask) and <math><semantics><mrow><mi>S</mi><mo>(</mo><mi>p</mi><mo separator="true">,</mo><mi>m</mi><mi>a</mi><mi>s</mi><mi>k</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">S(p,mask)</annotation></semantics></math>S(p,mask) be the count and sum of numbers with prefix before <math><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p-th digit contains different digits denoted by <math><semantics><mrow><mi>m</mi><mi>a</mi><mi>s</mi><mi>k</mi></mrow><annotation encoding="application/x-tex">mask</annotation></semantics></math>mask. At this moment the sum only consider suffix starting from <math><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p. If we choose some digit <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i at position <math><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p, the sum will add two parts, one is remaining suffix starting from <math><semantics><mrow><mi>p</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">p+1</annotation></semantics></math>p+1 after <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i is chosen, the other is the digit <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>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)

コメント

コメントを投稿