fork 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. ll fp(ll b, ll p) {
  11. 	if (!p) return 1;
  12. 	ll res = fp(b, p >> 1);
  13. 	return res * res % M * (p & 1 ? b % M : 1) % M;
  14. }
  15.  
  16. int mp1[N], mp2[1 << (10 + DIGITS)];
  17.  
  18. vector<int> freq(int c) {
  19. 	vector<int> f(10);
  20. 	if (!c) return f;
  21. 	int x = 0;
  22. 	for (int i = 10 + DIGITS - 1; i >= 0; i--) {
  23. 		if ((c >> i & 1) == 0) {
  24. 			x++;
  25. 		} else if (x < 10) f[x]++;
  26. 	}
  27. 	return f;
  28. }
  29.  
  30. int val(vector<int> &f) {
  31. 	int x = DIGITS, res = 0;
  32. 	for (int &i: f) {
  33. 		res <<= i + 1;
  34. 		res |= (1 << i) - 1;
  35. 		x -= i;
  36. 	}
  37. 	res = (res << (x + 1)) | ((1 << x) - 1);
  38. 	return res;
  39. }
  40.  
  41. ll fact[15], ones[15], inv[15];
  42. string n;
  43. ll dp[DIGITS + 1][N][2];
  44. int vis[DIGITS + 1][N][2], id;
  45.  
  46.  
  47. ll f(int i, int c, bool ls) {
  48. 	auto &ans = dp[i][c][ls];
  49. 	auto &vid = vis[i][c][ls];
  50. 	if ((ls && vid) || vid == id) return ans;
  51. 	vid = id, ans = 0;
  52. 	auto ff = freq(mp1[c]);
  53. 	if (i == DIGITS) {
  54. 		int cnt = 0;
  55. 		for (int x = 0; x < 10; x++)
  56. 			ans += x * ff[x], cnt += ff[x];
  57. 		ans = ans % M * ones[cnt] % M * fact[cnt - 1] % M;
  58. 		for (auto &x: ff)
  59. 			ans = ans * inv[x] % M;
  60. 		return ans;
  61. 	}
  62. 	for (int x = 0; x <= (ls ? 9 : n[i] - '0'); x++) {
  63. 		if (c || x) ff[x]++;
  64. 		int cc = mp2[val(ff)];
  65. 		ans = (ans + f(i + 1, cc, ls || x < n[i] - '0')) % M;
  66. 		if (c || x) ff[x]--;
  67. 	}
  68. 	return ans;
  69. }
  70.  
  71. int getN() {
  72. 	int c = 0;
  73. 	string p = string(10, '0') + string(DIGITS, '1');
  74. 	while (next_permutation(p.begin(), p.end())) c++;
  75. 	return c;
  76. }
  77.  
  78. signed main() {
  79. 	cin.tie(0)->sync_with_stdio(0);
  80. #if Mosaab
  81. 	freopen("input.txt", "r", stdin);
  82. 	freopen("output.txt", "w", stdout);
  83. #endif
  84.  
  85. 	// return cout << getN(), 0;
  86.  
  87. 	fact[0] = 1;
  88. 	for (int i = 1; i < 15; i++) {
  89. 		fact[i] = fact[i - 1] * i % M;
  90. 		ones[i] = (ones[i - 1] * 10 + 1) % M;
  91. 	}
  92. 	inv[14] = fp(fact[14], M - 2);
  93. 	for (int i = 14; i > 0; i--) {
  94. 		inv[i - 1] = inv[i] * i % M;
  95. 	}
  96.  
  97. 	string p = string(10, '0') + string(DIGITS, '1');
  98. 	for (int i = 0; i < N; i++) {
  99. 		int x = bitset<DIGITS + 10>(p).to_ulong();
  100. 		mp1[i] = x, mp2[x] = i;
  101. 		next_permutation(p.begin(), p.end());
  102. 	}
  103.  
  104. 	int t;
  105. 	cin >> t;
  106. 	vector<pair<ll, ll> > a(t);
  107. 	map<ll, ll> ans;
  108. 	for (auto &[l,r]: a) {
  109. 		cin >> l >> r;
  110. 		ans[r], ans[l - 1];
  111. 	}
  112.  
  113. 	for (auto &[i,j]: ans) {
  114. 		n = to_string(i);
  115. 		if (n.size() < DIGITS)
  116. 			n = string(DIGITS - n.size(), '0') + n;
  117. 		id++, j = f(0, 0, 0);
  118. 	}
  119.  
  120. 	for (auto &[l,r]: a) {
  121. 		cout << (ans[r] - ans[l - 1] + M) % M << el;
  122. 	}
  123. }
  124.  
Success #stdin #stdout 0.16s 143200KB
comments (?)
stdin
copy 
2
1 12
10 1223455567
stdout
copy 
100
313623365
https://ideone.com/136Y2W
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!