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. vector<int> digit;  
  12.  
  13. vector<int> getDigit(ll n, int base) {
  14. 	vector<int> ans; 
  15. 	for (; n > 0; n /= base) ans.push_back(n % base); 
  16. 	return ans; 
  17. }
  18.  
  19. // dp = Xét ở hệ cơ số base, Số lượng số của phần còn lại thoả mãn điều kiện khi
  20. // 	    phần prefix ở trước vị trí idx mang theo điều kiện leading, smaller 
  21. //	    và mask đại diện cho tính chẵn lẻ của số lần xuất hiện của mỗi chữ số
  22. //       							
  23. ll memo[11][60][2][2][1 << 10]; 
  24.  
  25. ll dp(int base, int idx, bool leading, bool smaller, int mask) {
  26. 	if (idx == -1) return (mask == 0);   
  27.  
  28. 	ll& ans = memo[base][idx][leading][smaller][mask];
  29. 	if (ans != -1 && smaller) return ans; 
  30.  
  31. 	ans = 0;   
  32. 	int max_digit = (smaller) ? base - 1 : digit[idx];   
  33. 	for (int i = 0; i <= max_digit; i++) {
  34. 		bool new_leading = leading & (i == 0);   
  35. 		int new_mask = (new_leading) ? mask : mask ^ (1 << i); 
  36. 		ans += dp(base, idx - 1, new_leading, smaller | (i < digit[idx]), new_mask);
  37. 	}
  38.  
  39. 	return ans; 
  40. }
  41.  
  42. ll solve(ll n, int base) {
  43. 	digit = getDigit(n, base); 
  44. 	return dp(base, digit.size() - 1, 1, 0, 0); 
  45. }
  46.  
  47. // Ta sẽ memset mảng memo 1 lần duy nhất, và "lấp đầy" trước mảng memo 
  48. // bằng cách gọi hàm solve(1e18, base) cho mọi base từ 2 đến 10
  49. // Nhưng lưu ý lúc return giá trị dp thì phải thêm điều kiện smaller
  50. // Chi phí precompute: O(10^2 * log2(n) * 2 * 2 * 2^10)
  51. // Khi đó độ phức tạp cho mỗi truy vấn sẽ chỉ còn tốn O(log2(n) * 10)
  52. void precompute() {
  53. 	memset(memo, -1, sizeof memo);  
  54.  
  55. 	for (int base = 2; base <= 10; base++) {
  56. 		ll foo = solve(1e18, base); 
  57. 	}
  58. }
  59.  
  60. int main() {
  61. 	ios::sync_with_stdio(false); 
  62. 	cin.tie(nullptr); 
  63. 	precompute();  
  64.  
  65. 	int q; 
  66. 	cin >> q; 
  67.  
  68. 	while (q--) {
  69. 		int b; ll l, r;  
  70. 		cin >> b >> l >> r; 
  71. 		ll ans = solve(r, b) - solve(l - 1, b); 
  72. 		cout << ans << '\n'; 
  73. 	}
  74. }
Success #stdin #stdout 0.01s 24644KB
comments (?)
stdin
copy 
2
2 4 9
3 1 10
stdout
copy 
1
2
https://ideone.com/JpiZH5
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!