fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int MOD = 998244353; 
  12.  
  13. void add(int& a, int b) {
  14. 	(a += b) %= MOD; 
  15. }
  16.  
  17. vector<int> digit; 
  18.  
  19. vector<int> getDigit(ll n) {
  20. 	vector<int> ans; 
  21. 	for (; n > 0; n /= 10) ans.push_back(n % 10); 
  22. 	return ans; 
  23. }
  24.  
  25. int pow10[18]; 
  26.  
  27. // dp = {tổng các số, số lượng số}
  28. // mask là tập hợp các chữ số đã xuất hiện
  29. ii memo[18][2][2][1 << 10];  
  30.  
  31. ii dp(int idx, bool leading, bool smaller, int mask, int k) {
  32. 	if (idx == -1) return {0, 1};   
  33.  
  34. 	ii& ans = memo[idx][leading][smaller][mask];
  35. 	if (ans.first != -1) return ans; 
  36.  
  37. 	ans = {0, 0};  
  38. 	int max_digit = (smaller) ? 9 : digit[idx]; 
  39. 	for (int i = 0; i <= max_digit; i++) {
  40. 		bool new_leading = leading & (i == 0); 
  41. 		int next_mask = (new_leading) ? mask : (mask | (1 << i));  
  42.  
  43. 		if (__builtin_popcount(next_mask) > k) continue; 
  44.  
  45. 		ii next_ans = dp(idx - 1, new_leading, smaller | (i < digit[idx]), next_mask, k); 
  46. 		add(ans.first, next_ans.first);
  47. 		add(ans.first, 1ll * pow10[idx] * i % MOD * next_ans.second % MOD);   
  48. 		add(ans.second, next_ans.second); 
  49. 	}
  50.  
  51. 	return ans; 
  52. }
  53.  
  54. int solve(ll n, int k) {
  55. 	digit = getDigit(n); 
  56. 	memset(memo, -1, sizeof memo); 
  57. 	return dp(digit.size() - 1, 1, 0, 0, k).first; 
  58. }
  59.  
  60. int main() {
  61. 	ios::sync_with_stdio(false); 
  62. 	cin.tie(nullptr); 	
  63. 	ll l, r; int k; 
  64. 	cin >> l >> r >> k; 
  65.  
  66. 	pow10[0] = 1; 
  67. 	for (int i = 1; i <= 17; i++) pow10[i] = 1ll * pow10[i - 1] * 10 % MOD; 
  68.  
  69. 	int ans = solve(r, k) - solve(l - 1, k); 
  70. 	if (ans < 0) ans += MOD; 
  71.  
  72. 	cout << ans << '\n'; 
  73. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
101 154 2
stdout
copy 
2189
https://ideone.com/JU3LHU
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!