fork(4) download
copy 
  1. /*Ankit and Race Team*/
  2. //by Tanmay Chaudhari
  3. #ifdef _MSC_VER
  4. #define _CRT_SECURE_NO_WARNINGS
  5. #endif
  6. //#pragma comment(linker, "/STACK:66777216")
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define si(a)				scanf("%d",&a)
  11. #define sl(a)				scanf("%lld",&a)
  12. #define pi(a)				printf("%d\n",a)
  13. #define pl(a)				printf("%lld\n",a)
  14.  
  15. typedef long long			LL;
  16. typedef vector<int>			vi;
  17. typedef pair<int, int>		ii;
  18. typedef vector<vi>			vvi;
  19. typedef vector<ii>			vii;
  20.  
  21. #define SET(a,b)			memset(a,b,sizeof(a))	
  22. #define forall(i,a,b)		for(int i=a; i<b; i++)
  23. #define forrev(i,a,b)		for(int i=a; i>=b; i--)
  24. #define forr(it,container)  for(auto it=container.begin(); it!=container.end(); it++)
  25. #define w(t)				int t;si(t);while(t--)
  26.  
  27. #define TRACE
  28.  
  29. #ifdef TRACE
  30. #define trace1(x)                cerr << #x << ": " << x << endl;
  31. #define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  32. #define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  33. #define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  34. #define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  35. #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  36.  
  37. #else
  38.  
  39. #define trace1(x)
  40. #define trace2(x, y)
  41. #define trace3(x, y, z)
  42. #define trace4(a, b, c, d)	
  43. #define trace5(a, b, c, d, e)
  44. #define trace6(a, b, c, d, e, f)
  45.  
  46. #endif
  47.  
  48. const int MOD = 1e9 + 7;
  49. LL arr[1 << 20];
  50.  
  51. #define N 2123456
  52.  
  53. LL fac[N], ifac[N];
  54.  
  55. LL PowerMod(LL a, LL n){
  56. 	LL ret = 1;
  57. 	while (n){
  58. 		if (n & 1){
  59. 			ret *= a;
  60. 			ret %= MOD;
  61. 		}
  62. 		a *= a;
  63. 		a %= MOD;
  64. 		n /= 2;
  65. 	}
  66. 	return ret;
  67. }
  68.  
  69. inline void precompute(){
  70. 	int i;
  71. 	fac[0] = 1;
  72. 	for (i = 1; i < N; i++){
  73. 		fac[i] = (i * fac[i - 1]) % MOD;
  74. 	}
  75. 	ifac[N - 1] = PowerMod(fac[N - 1], MOD - 2);
  76. 	for (i = N - 2; i >= 0; i--){
  77. 		ifac[i] = ((i + 1) * ifac[i + 1]) % MOD;
  78. 	}
  79. }
  80.  
  81. LL com(int n, int r){
  82. 	LL ret = fac[n];
  83. 	ret *= ifac[r];
  84. 	ret %= MOD;
  85. 	ret *= ifac[n - r];
  86. 	ret %= MOD;
  87. 	return ret;
  88. }
  89.  
  90.  
  91. int main()
  92. {
  93. 	//freopen("input.txt","r",stdin);
  94. 	//freopen("output.txt","w",stdout);
  95. 	precompute();
  96. 	int t;
  97. 	LL n, k, ans;
  98. 	si(t);
  99. 	while (t--)
  100. 	{
  101. 		ans = 0;
  102. 		sl(n); sl(k);
  103. 		for (int i = 0; i < n; i++)
  104. 			sl(arr[i]);
  105. 		sort(arr, arr + n);
  106. 		for (int i = 0; i < n - k + 1; i++)
  107. 		{
  108. 			LL temp;
  109. 			temp = com(n - i - 1, k - 1);
  110. 			temp = (temp*arr[i]) % MOD;
  111. 			ans = (ans + temp) % MOD;
  112. 		}
  113. 		pl(ans);
  114. 	}
  115. 	return 0;
  116. }
Runtime error #stdin #stdout 0.24s 44832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0LvDhK
language:
C++14 (gcc 8.3)
created:
8 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!