?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
60403673 |
Practice: beginner1010 |
1073E - 12 | C++14 (GCC 6-32) | Accepted | 46 ms | 660 KB | 2019-09-11 20:40:55 | 2019-09-11 20:40:55 |
#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))); }
?
?
?
?