Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
60403673 Practice:
beginner1010
1073E - 12 GNU C++14 Accepted 46 ms 660 KB 2019-09-11 20:40:55 2019-09-11 20:40:55
 
 
→ Source
#include <iostream>
#include <cstring>
using namespace std;

const int mod = 998244353;
const int MAX_LENGTH = 20;
int bound [MAX_LENGTH];
long long l, r;
int k;
pair<int,int> dp[2][2][MAX_LENGTH][1 << 10];
int bit_count[1 << 10];
int ten_pow[MAX_LENGTH];

int mul(long long a, int b){ return (a * b) % mod; }
int add(long long a, int b) {
    a += b;
    if (a < 0) a += mod;
    if (a >= mod) a -= mod;
    return a;
}

void digitize(long long num) {
    for(int i = 0; i < MAX_LENGTH; i ++) {
        bound[i] = num % 10;
        num /= 10;
    }
    return;
}

pair<int,int> rec(int smaller, int start, int pos, int mask) {
    if (bit_count[mask] > k)
        return make_pair(0, 0);
    if (pos == -1)
        return make_pair(0, 1);

    if (dp[smaller][start][pos][mask].first != -1)
        return dp[smaller][start][pos][mask];

    int res_sum, res_ways;
    res_sum = res_ways = 0;
    for (int digit = 0; digit < 10; digit ++) {
        if (smaller == 0 && digit > bound[pos])
            continue;
        int new_smaller = smaller | (digit < bound[pos]);
        int new_start = start | (digit > 0) | (pos == 0);
        int new_mask = new_start == 1? (mask | (1 << digit)): 0;

        pair<int,int> cur = rec(new_smaller, new_start, pos - 1, new_mask);
        int cur_sum = cur.first;
        int cur_ways = cur.second;
        res_sum = add(res_sum, add(mul(mul(digit, ten_pow[pos]), cur_ways), cur_sum));
        res_ways = add(res_ways, cur_ways);
    }

    dp[smaller][start][pos][mask] = make_pair(res_sum, res_ways);
    return dp[smaller][start][pos][mask];
}

int solve(long long upper_bound) {
    memset(dp, -1, sizeof(dp));
    digitize(upper_bound);
    pair<int,int> ans = rec(0, 0, MAX_LENGTH - 1, 0);
    return ans.first;
}

int main() {
    scanf("%lld%lld%d", &l, &r, &k);
    
    bit_count[0] = 0;
    for(int i = 1; i < (1 << 10); i ++) {
        bit_count[i] = bit_count[i & (i - 1)] + 1;
    }
    
    ten_pow[0] = 1;
    for(int i = 1; i < MAX_LENGTH; i ++) {
        ten_pow[i] = mul(ten_pow[i - 1], 10);
    }
    printf("%d\n", add(solve(r), -solve(l - 1)));
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details