fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long t, n, m, ans, dp[17][2][2][2];
  5. bool ye;
  6. string s, l, r;
  7. char a[18];
  8.  
  9. //slv(0, 0, 0, 0) -> banyak bilangan di antara R yang consist matching string
  10. long long slv(long long id, bool kurangR, bool lebihL, bool aman)
  11. {
  12. 	//kurangR = 1 boleh milih digit yang lebih gede dari digit R sekarang
  13. 	//lebihL = 1 boleh milih digit yang lebih kecil dari digit L sekarang
  14. 	//kalo di interval matching string harus pilih digit yang sesuai
  15. 	//gara-gara kasus S = 0 aku harus tambah state masih leading zero atau ngga (aman) asem
  16. 	//Dan aku baru sadar, kenapa aku ga hitungnya dengan cara kontribusi(0, R)-kontribusi(0, L-1)
  17. 	if (dp[id][kurangR][lebihL][aman] != -1) return dp[id][kurangR][lebihL][aman];
  18. 	if (id == m) return 1;
  19. 	long long d;
  20. 	dp[id][kurangR][lebihL][aman] = 0;
  21. 	for (d=0; d<=9; d++)
  22. 	{
  23. 		if ((!lebihL && d<l[id]-'0') || (!kurangR && d>r[id]-'0') || (a[id] != '#' && a[id]-'0' != d) || (!aman && a[id] == '0')) continue; // ga boleh
  24. 		dp[id][kurangR][lebihL][aman] += slv(id+1, kurangR|(d<r[id]-'0'), lebihL|(d>l[id]-'0'), aman|(d>0));
  25. 	}
  26. 	return dp[id][kurangR][lebihL][aman];
  27. }
  28.  
  29. int main()
  30. {
  31. 	long long i, j, ii;
  32. 	scanf("%lld", &t);
  33. 	while (t--)
  34. 	{
  35. 		cin >> s >> l >> r;
  36. 		n = s.length();
  37. 		m = r.length();
  38. 		reverse(l.begin(), l.end());
  39. 		while (l.size()<m) l.push_back('0');
  40. 		reverse(l.begin(), l.end());
  41. 		ans = 0;
  42. 		for (i=0; i<m-n+1; i++)
  43. 		{
  44. 			//cek di subtring i sampai i+n-1
  45. 			if (i == 0 && s[0] == '0') continue; // ga boleh ada leazing zero ngabs
  46. 			for (j=0; j<m; j++)
  47. 			{
  48. 				if (j>=i && j<=i+n-1)
  49. 				{
  50. 					//sekarang posisi ke j-i di string s
  51. 					a[j] = s[j-i];
  52. 				} else 
  53. 				{
  54. 					a[j] = '#';
  55. 				}
  56. 			}
  57. 			memset(dp, -1, sizeof(dp));
  58. 			ans += slv(0, 0, 0, 0); //kontribusi string s di antara L dan R di substring [i, i+n-1]
  59. 		}
  60. 		printf("%lld\n", ans);
  61. 	}
  62. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
6
22 23 234
0295 295 295
0 1 9999999999999999
2718 998244353 9982443530000000
869120 1234567890123456 2345678901234567
2023032520230325 1 9999999999999999
stdout
copy 
12
0
14888888888888889
12982260572545
10987664021
1
https://ideone.com/OBcO5P
language:
C++ (gcc 8.3)
created:
11 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!