fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. //#pragma GCC optimize ("O3")
  5. //#pragma GCC target ("sse4")
  6.  
  7. using namespace std;
  8. template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
  9. template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
  10. const int MAXN = (1 << 20);
  11.  
  12. int n;
  13. bool can[10];
  14.  
  15. void read()
  16. {
  17. 	cin >> n;
  18.  
  19. 	string t;
  20. 	cin >> t;
  21.  
  22. 	for(char c: t)
  23. 		can[c - '0'] = 1;
  24. }
  25.  
  26. int64_t d[10][30][20][10][10];
  27.  
  28. int64_t rec(int i, int c2, int c3, int c5, int c7)
  29. {
  30. 	if(c2 < 0) return 0;
  31. 	if(c3 < 0) return 0;
  32. 	if(c5 < 0) return 0;
  33. 	if(c7 < 0) return 0;
  34. 	if(i == n)
  35. 		return c2 + c3 + c5 + c7 == 0;
  36.  
  37. 	int64_t &memo = d[i][c2][c3][c5][c7];
  38. 	if(memo != -1)
  39. 		return memo;
  40.  
  41. 	memo = 0;
  42. 	for(int d = 1; d < 10; d++)
  43. 		if(can[d])	
  44. 		{
  45. 			int n2 = c2, n3 = c3, n5 = c5, n7 = c7;
  46.  
  47. 			int x = d;
  48. 			while(x % 2 == 0) n2--, x /= 2;
  49. 			while(x % 3 == 0) n3--, x /= 3;
  50. 			while(x % 5 == 0) n5--, x /= 5;
  51. 			while(x % 7 == 0) n7--, x /= 7;
  52.  
  53. 			memo += rec(i + 1, n2, n3, n5, n7);
  54. 		}
  55.  
  56. 	return memo;
  57. }
  58.  
  59. int64_t sq(int64_t x) { return x * x; }
  60.  
  61. void solve()
  62. {
  63. 	int64_t answer = 0;
  64. 	if(can[0])
  65. 	{
  66. 		int64_t numb1 = 1, rem = 1;
  67. 		int cnt_av = 0;
  68. 		for(int i = 1; i < 10; i++)
  69. 			if(can[i]) cnt_av++;
  70.  
  71. 		for(int i = 0; i < n; i++)
  72. 		{
  73. 			numb1 *= (cnt_av + 1);
  74. 			rem *= cnt_av;
  75. 		}
  76.  
  77. 		answer += (numb1 - rem) * (numb1 - rem); 
  78. 	}
  79.  
  80. 	memset(d, -1, sizeof(d));
  81. 	for(int c2 = 0; c2 < 30; c2++)
  82. 		for(int c3 = 0; c3 < 20; c3++)
  83. 			for(int c5 = 0; c5 < 10; c5++)
  84. 				for(int c7 = 0; c7 < 10; c7++)
  85. 					answer += sq(rec(0, c2, c3, c5, c7));
  86.  
  87. 	cout << answer << endl;
  88. }
  89.  
  90. int main()
  91. {
  92. 	ios_base::sync_with_stdio(false);
  93. 	cin.tie(NULL);
  94.  
  95. 	read();
  96. 	solve();
  97. 	return 0;
  98. }
  99.  
  100.  
Success #stdin #stdout 0s 19928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/KyxJuz
language:
C++14 (gcc 8.3)
created:
6 years 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!