fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5.  
  6. const int LIM = 10;
  7.  
  8. void show_all_permutations(int init_digits_flag) {
  9. 	std::vector<int> nums, idx;
  10.  
  11. 	while (init_digits_flag > 0) {
  12. 		nums.push_back(init_digits_flag % 10);
  13. 		init_digits_flag /= 10;
  14. 	}
  15. 	for (int i = 0; i < LIM; i++)
  16. 		idx.push_back(i);
  17.  
  18. 	std::set<int> digits_flags;
  19. 	do {
  20. 		int flag = 0;
  21. 		for (int new_id: idx)
  22. 			flag = flag * 10 + nums[new_id];
  23.  
  24. 		if (digits_flags.find(flag) == digits_flags.end()) {
  25. 			for (int new_id: idx)
  26. 				std::cout << nums[new_id] << " ";
  27. 			std::cout << "\n";
  28.  
  29. 			digits_flags.insert(flag);
  30. 		}
  31. 	} while (std::next_permutation(idx.begin(), idx.end()));
  32. }
  33.  
  34. int f[11][101][10];
  35. // f[i][k][l]: đếm số cách biểu diễn k dưới dạng tổng bình phương của i số
  36. // trong khoảng [1, 9]; i số tạo thành dãy tăng dần mà số cuối cùng là l
  37.  
  38. void init_f() {
  39. 	for (int l = 0; l <= 9; l++) {
  40. 		for (int k = 0; k <= 100; k++)
  41. 			for (int i = 0; i <= 10; i++)
  42. 				f[i][k][l] = 0;
  43.  
  44. 		f[1][l*l][l] = 1;
  45. 	}
  46.  
  47. 	for (int i = 2; i <= 10; i++) {
  48. 		for (int l1 = 1; l1 <= 9; l1++)
  49. 			for (int l2 = l1; l2 <= 9; l2++) 
  50. 				for (int k = l2*l2+l1*l1; k <= 100; k++) {
  51. 					f[i][k][l2] += f[i-1][k-l2*l2][l1];
  52. 				}
  53. 	}
  54. }
  55.  
  56. void trace(int n, int x_cnt, int number_flags) {
  57. 	if (x_cnt == 0) {
  58. 		show_all_permutations(number_flags);
  59. 	} else {
  60. 		for (int l = 9; l >= 1; l--)
  61. 			if (f[x_cnt][n][l] > 0)
  62. 				trace(n-l*l, x_cnt-1, number_flags*10+l);
  63. 	}
  64. }
  65.  
  66. int main() {
  67. 	init_f();
  68.  
  69. 	int n;
  70. 	std::cin >> n;
  71.  
  72. 	int ans = 0;
  73. 	for (int l = 1; l <= 10; l++)
  74. 		ans += f[10][n][l];
  75.  
  76. 	if (ans == 0)
  77. 		std::cout << "-1\n";
  78. 	else {
  79. 		std::cout << ans << "\n";
  80. 		// trace(n, 10, 0);
  81. 	}
  82. }
Success #stdin #stdout 0s 15280KB
comments (?)
stdin
copy 
100
stdout
copy 
24
https://ideone.com/ltaShJ
https://d...content-available-to-author-only...c.com/t/89760/
language:
C++ (gcc 8.3)
created:
4 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!