fork(1) download
copy 
  1. // عَجَبًا لأَمْرِ المُؤْمِنِ، إنَّ أمْرَهُ كُلَّهُ خَيْرٌ
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. const char el = '\n';
  7.  
  8. const int N = 646646, M = 998244353, DIGITS = 12;
  9.  
  10. // fast power
  11. ll fp(ll b, ll p) {
  12. 	if (!p) return 1;
  13. 	ll res = fp(b, p >> 1);
  14. 	return res * res % M * (p & 1 ? b % M : 1) % M;
  15. }
  16.  
  17. // mp1[x] = the x-th frequency permutation
  18. // mp2[x] = the order of the frequency permutation that is x in base-10
  19. int mp1[N], mp2[1 << (10 + DIGITS)];
  20.  
  21. // converts the frequency permutation into one base-10 compressed number
  22. int val(vector<int> &f) {
  23. 	int x = DIGITS, res = 0;
  24. 	for (int &i: f) {
  25. 		res <<= i + 1;
  26. 		res |= (1 << i) - 1;
  27. 		x -= i;
  28. 	}
  29. 	res = (res << (x + 1)) | ((1 << x) - 1);
  30. 	return res;
  31. }
  32.  
  33. // converts back the base-10 compression into frequency permutation
  34. vector<int> freq(int c) {
  35. 	vector<int> f(10);
  36. 	if (!c) return f;
  37. 	int x = 0;
  38. 	for (int i = 10 + DIGITS - 1; i >= 0; i--) {
  39. 		if ((c >> i & 1) == 0) {
  40. 			x++;
  41. 		} else if (x < 10) f[x]++;
  42. 	}
  43. 	return f;
  44. }
  45.  
  46. // factorial, inverse factorial, ones[i] = 11...1 i times
  47. ll fact[15], ones[15], inv[15];
  48. // dp definitions
  49. string n;
  50. ll dp[DIGITS + 1][N][2];
  51. int vis[DIGITS + 1][N][2], id;
  52.  
  53. // dp calculation
  54. ll f(int i, int c, bool ls) {
  55. 	auto &ans = dp[i][c][ls];
  56. 	auto &vid = vis[i][c][ls];
  57. 	if ((ls && vid) || vid == id) return ans;
  58. 	vid = id, ans = 0;
  59.  
  60. 	// get the frequency from the base-10 compression
  61. 	auto ff = freq(mp1[c]);
  62.  
  63. 	// base case calculation
  64. 	if (i == DIGITS) {
  65. 		int cnt = 0;
  66. 		for (int x = 0; x < 10; x++)
  67. 			ans += x * ff[x], cnt += ff[x];
  68. 		ans = ans % M * ones[cnt] % M * fact[cnt - 1] % M;
  69. 		for (auto &x: ff)
  70. 			ans = ans * inv[x] % M;
  71. 		return ans;
  72. 	}
  73.  
  74. 	// dp transitions
  75. 	for (int x = 0; x <= (ls ? 9 : n[i] - '0'); x++) {
  76. 		// updating frequency
  77. 		if (c || x) ff[x]++;
  78. 		// compressing frequency
  79. 		int cc = mp2[val(ff)];
  80. 		// doing transition
  81. 		ans = (ans + f(i + 1, cc, ls || x < n[i] - '0')) % M;
  82. 		// undoing frequency update
  83. 		if (c || x) ff[x]--;
  84. 	}
  85. 	return ans;
  86. }
  87.  
  88. // helper function to know the needed N for this DIGITS, e.g. 10^12 -> 646646
  89. int getN() {
  90. 	int c = 0;
  91. 	string p = string(10, '0') + string(DIGITS, '1');
  92. 	while (next_permutation(p.begin(), p.end())) c++;
  93. 	return c;
  94. }
  95.  
  96. signed main() {
  97. 	cin.tie(0)->sync_with_stdio(0);
  98. #if Mosaab
  99. 	freopen("input.txt", "r", stdin);
  100. 	freopen("output.txt", "w", stdout);
  101. #endif
  102.  
  103. 	// return cout << getN(), 0;
  104.  
  105. 	// filling factorial and inverses
  106. 	fact[0] = 1;
  107. 	for (int i = 1; i < 15; i++) {
  108. 		fact[i] = fact[i - 1] * i % M;
  109. 		ones[i] = (ones[i - 1] * 10 + 1) % M;
  110. 	}
  111. 	inv[14] = fp(fact[14], M - 2);
  112. 	for (int i = 14; i > 0; i--) {
  113. 		inv[i - 1] = inv[i] * i % M;
  114. 	}
  115.  
  116. 	// maping all possible frequencies into compressed base-10 form and vice versa
  117. 	string p = string(10, '0') + string(DIGITS, '1');
  118. 	for (int i = 0; i < N; i++) {
  119. 		int x = bitset<DIGITS + 10>(p).to_ulong();
  120. 		mp1[i] = x, mp2[x] = i;
  121. 		next_permutation(p.begin(), p.end());
  122. 	}
  123.  
  124. 	// processing test cases in terms of increasing l,r value
  125. 	int t;
  126. 	cin >> t;
  127. 	vector<pair<ll, ll> > a(t);
  128. 	map<ll, ll> ans;
  129. 	for (auto &[l,r]: a) {
  130. 		cin >> l >> r;
  131. 		ans[r], ans[l - 1];
  132. 	}
  133.  
  134. 	for (auto &[i,j]: ans) {
  135. 		n = to_string(i);
  136. 		if (n.size() < DIGITS)
  137. 			n = string(DIGITS - n.size(), '0') + n;
  138. 		id++, j = f(0, 0, 0);
  139. 	}
  140.  
  141. 	for (auto &[l,r]: a) {
  142. 		cout << (ans[r] - ans[l - 1] + M) % M << el;
  143. 	}
  144. }
  145.  
Success #stdin #stdout 0.18s 147348KB
comments (?)
stdin
copy 
2
1 12
10 1223455567
stdout
copy 
100
313623365
https://ideone.com/QAGiXj
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

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!