fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. const int kMod = 1e9+7, kMaxN = 1e5+5;
  7.  
  8. int pow(int a, int p) {
  9. 	int rez = 1;
  10. 	while (p) {
  11. 		if (p & 1) {
  12. 			rez = (1LL * rez * a) % kMod;
  13. 		}
  14. 		a = (1LL * a * a) % kMod;
  15. 		p >>= 1;
  16. 	}
  17. 	return rez;
  18. }
  19.  
  20. int fact[kMaxN], inv_fact[kMaxN];
  21. int num_ways[kMaxN];
  22.  
  23. void init() {
  24. 	fact[0] = 1;
  25. 	for (int i = 1; i < kMaxN; i += 1) {
  26. 		fact[i] = (1LL * fact[i - 1] * i) % kMod;
  27. 	}
  28.  
  29. 	inv_fact[kMaxN - 1] = pow(fact[kMaxN - 1], kMod - 2);
  30. 	inv_fact[0] = 1;
  31.  
  32. 	for (int i = kMaxN - 2; i; i -= 1) {
  33. 		inv_fact[i] = (1LL * (i + 1) * inv_fact[i + 1]) % kMod;
  34. 	}
  35.  
  36. 	num_ways[1] = 1;
  37. 	for (int i = 2; i < kMaxN; i += 1) {
  38. 		int current_ways = (1LL * i * (i - 1) / 2) % kMod;
  39. 		num_ways[i] = (1LL * num_ways[i - 1] * current_ways) % kMod;
  40. 	}
  41. }
  42.  
  43. int comb(int n, int k) {
  44. 	int rez = 1;
  45. 	rez = (1LL * rez * fact[n]) % kMod;
  46. 	rez = (1LL * rez * inv_fact[k]) % kMod;
  47. 	rez = (1LL * rez * inv_fact[n - k]) % kMod;
  48. 	return rez;
  49. }
  50.  
  51. int main() {
  52. 	init();
  53.  
  54. 	int n; cin >> n;
  55. 	vector<int> elements;
  56. 	for (int i = 1; i <= n; i += 1) {
  57. 		int x; cin >> x;
  58. 		elements.push_back(x);
  59. 	}
  60.  
  61. 	int answer = 1;
  62.  
  63. 	sort(elements.begin(), elements.end());
  64. 	for (int left = 0; left < int(elements.size()); ) {
  65. 		int right = left;
  66. 		while (right < int(elements.size()) and elements[left] == elements[right]) {
  67. 			right += 1;
  68. 		}
  69.  
  70. 		int bonus = 0;
  71.  
  72. 		if (left == 0) {
  73. 			bonus = 1;
  74. 		} else {
  75. 			// O(N) overall
  76. 			for (int un_matched = 1; un_matched <= right - left; un_matched += 1) {
  77. 				int matched = right - left - un_matched;
  78. 				bonus = (bonus + 1LL * comb(left + matched - 1, matched) * un_matched) % kMod;
  79. 			}
  80. 		}
  81. 		cout << right - left << ' ' << num_ways[right - left] << '\n';
  82. 		bonus = (1LL * bonus * num_ways[right - left]) % kMod;
  83. 		answer = (1LL * answer * bonus) % kMod;
  84.  
  85. 		left = right;
  86. 	}
  87.  
  88. 	cout << answer << '\n';
  89. 	return 0;
  90. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
12
3 9 0 7 0 7 9 0 7 9 7 3
stdout
copy 
3 3
2 1
4 18
3 3
4490640
https://ideone.com/CnEohh
language:
C++14 (gcc 8.3)
created:
13 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!