fork(1) download
copy 
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <vector>
  4. using namespace std;
  5. const int MOD = 1000000007;
  6. const int MAX = 1000005;
  7. vector<int> dp[MAX];
  8. int a[MAX];
  9. void add(int &a, int b)
  10. {
  11. 	a += b;
  12. 	if (a >= MOD)
  13. 		a -= MOD;
  14. }
  15. int main()
  16. {
  17. 	int n, k;
  18. 	long long l;
  19. 	scanf("%d %lld %d", &n, &l, &k);
  20. 	for (int i = 0; i < n; i++)
  21. 		dp[i].resize(k + 1);
  22. 	vector<int> vals;
  23. 	for (int i = 0; i < n; i++)
  24. 	{
  25. 		scanf("%d", a + i);
  26. 		vals.push_back(a[i]);
  27. 	}
  28. 	sort(vals.begin(), vals.end());
  29. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
  30. 	for (int i = 0; i < n; i++)
  31. 	{
  32. 		a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
  33. 		dp[i][1] = 1;
  34. 	}
  35. 	vector<int> cnt;
  36. 	cnt.resize(vals.size());
  37. 	for (int j = 2; j <= k; j++)
  38. 	{
  39. 		for (int i = 0; i < (int)cnt.size(); i++)
  40. 			cnt[i] = 0;
  41. 		for (int i = 0; i < n; i++)
  42. 			add(cnt[a[i]], dp[i][j - 1]);
  43. 		for (int i = 1; i < (int)cnt.size(); i++)
  44. 			add(cnt[i], cnt[i - 1]);
  45. 		for (int i = 0; i < n; i++)
  46. 			dp[i][j] = cnt[a[i]];
  47. 	}
  48. 	int ans = 0;
  49. 	for (int i = 0; i < n; i++)
  50. 		for (int j = 1; j <= k; j++)
  51. 		{
  52. 			long long b = l / n;
  53. 			if (i < l % n)
  54. 				b++;
  55. 			b = b - j + 1;
  56. 			if (b > 0)
  57. 				ans = (ans + (b % MOD) * dp[i][j]) % MOD;
  58. 		}
  59. 	printf("%d\n", ans);
  60. 	return 0;
  61. }
  62.  
Runtime error #stdin #stdout #stderr 0.48s 545792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/WNYKEz
language:
C++14 (gcc 8.3)
created:
8 years 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!