fork download 
  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. struct BigInt {	
  12. 	static const int BASE = 1e9; 
  13. 	static const int B = 9; 
  14.  
  15. 	vector<int> a; 
  16.  
  17. 	BigInt() {}
  18.  
  19. 	BigInt(ll x) {
  20. 		for (; x > 0; x /= BASE) {
  21. 			a.push_back(x % BASE); 
  22. 		}
  23. 	}
  24.  
  25. 	BigInt(const string &s) {
  26. 		for (int i = (int)s.size() - 1; i >= 0; i -= B) {
  27. 			int beg = max(0, i - B + 1); 
  28. 			int len = i - beg + 1;  
  29. 			int block = stoi(s.substr(beg, len)); 
  30. 			a.push_back(block); 
  31. 		}	
  32. 		trim();
  33. 	}
  34.  
  35. 	void trim() {
  36. 		while (!a.empty() && a.back() == 0) {
  37. 			a.pop_back(); 
  38. 		}
  39. 	}
  40.  
  41. 	bool isZero() {
  42. 		return (a.empty()); 
  43. 	}
  44.  
  45. 	BigInt operator+=(const BigInt &other) {
  46. 		int n = a.size(), m = other.a.size(); 
  47. 		int carry = 0; 
  48. 		for (int i = 0; i < max(n, m) || carry; i++) {
  49. 			if (i == a.size()) {
  50. 				a.push_back(0); 
  51. 			}
  52. 			a[i] += (i < m ? other.a[i] : 0) + carry; 
  53. 			carry = (a[i] >= BASE);   
  54. 			if (carry) a[i] -= BASE;   
  55. 		}	
  56. 		return *this; 
  57. 	}
  58.  
  59. 	BigInt operator*=(int b) {
  60. 		int n = a.size(); 
  61. 		int carry = 0; 
  62. 		for (int i = 0; i < n || carry; i++) {
  63. 			if (i == a.size()) {
  64. 				a.push_back(0); 
  65. 			}
  66. 			ll cur = 1ll * a[i] * b + carry; 
  67. 			a[i] = cur % BASE;  
  68. 			carry = cur / BASE; 
  69. 		}
  70. 		trim(); 
  71. 		return *this; 
  72. 	}
  73.  
  74. 	BigInt operator+(const BigInt &other) const {
  75. 		return BigInt(*this) += other; 
  76. 	}
  77.  
  78. 	BigInt operator*(int b) const {
  79. 		return BigInt(*this) *= b;  
  80. 	}
  81.  
  82. 	friend istream& operator>>(istream &in, BigInt &num) {
  83. 		string s;
  84. 		in >> s; 	
  85. 		num = BigInt(s);  
  86. 		return in; 
  87. 	}
  88.  
  89. 	friend ostream& operator<<(ostream &out, const BigInt &num) {
  90. 		out << (num.a.empty() ? 0 : num.a.back()); 
  91. 		for (int i = (int)num.a.size() - 2; i >= 0; i--) {
  92. 			out << setw(B) << setfill('0') << num.a[i]; 
  93. 		}
  94. 		return out; 
  95. 	}
  96. }; 
  97.  
  98. vector<int> digit;  
  99.  
  100. vector<int> getDigit(const string& s) {
  101. 	vector<int> ans; 
  102. 	for (int i = 0; i < s.size(); i++) {
  103. 		ans.push_back(s[i] - '0'); 
  104. 	}
  105. 	reverse(ans.begin(), ans.end()); 
  106. 	return ans; 
  107. }
  108.  
  109. // dp = {tổng các chữ số, số lượng số}
  110. bool vis[101][2];
  111. pair<BigInt, BigInt> memo[101][2]; 
  112.  
  113. pair<BigInt, BigInt> dp(int idx, bool smaller) {
  114. 	if (idx == -1) return {0, 1};  
  115.  
  116. 	pair<BigInt, BigInt>& ans = memo[idx][smaller];
  117. 	if (vis[idx][smaller]) return ans; 
  118. 	vis[idx][smaller] = true; 
  119.  
  120. 	ans = make_pair(0, 0);
  121. 	int max_digit = (smaller) ? 9 : digit[idx]; 
  122. 	for (int i = 0; i <= max_digit; i++) {
  123. 		pair<BigInt, BigInt> next_ans = dp(idx - 1, smaller | (i < digit[idx]));  
  124. 		ans.first += next_ans.first + next_ans.second * i; 
  125. 		ans.second += next_ans.second; 
  126. 	}
  127. 	return ans; 
  128. }
  129.  
  130. BigInt solve(const string& s) {
  131. 	digit = getDigit(s);  
  132. 	memset(vis, 0, sizeof vis); 
  133. 	return dp(digit.size() - 1, 0).first; 
  134. }
  135.  
  136. int main() {
  137. 	ios::sync_with_stdio(false); 
  138. 	cin.tie(nullptr);
  139. 	string s;
  140. 	cin >> s; 
  141. 	BigInt ans = solve(s); 
  142. 	cout << ans << '\n'; 
  143. }
  144.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin 
3
stdout 
6
https://ideone.com/99EaKl
language:
C++14 (gcc 8.3)
created:
192 days 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!