fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define LL long long
  5. #define VI vector<int>
  6. #define PII pair<int,int>
  7. #define F first
  8. #define S second
  9. #define pb push_back
  10. #define mp make_pair
  11. #define gc getchar
  12.  
  13. inline LL inp() {
  14.     char c = gc();
  15.     while(c<'0' || c>'9') c = gc();
  16.     LL ret = 0;
  17.     while(c>='0' && c<='9') {
  18.         ret = (ret << 3) + (ret << 1) + c - 48;
  19.         c = gc();
  20.     }
  21.     return ret;
  22. }
  23.  
  24. const int N = 1e6 + 10;
  25. const int MOD = 1e9 + 7;
  26. const int INF = 1e9 + 7;
  27.  
  28. int A[N]; pair<int,int> B[N];
  29. int num[N];
  30.  
  31. int main() {
  32. 	int n, k; LL l;
  33. 	n=inp(); l = inp(); k=inp();
  34. 	for(int i=0; i<n; i++) {
  35. 		A[i] = inp();
  36. 		B[i] = make_pair(A[i], i);
  37. 	}
  38.  
  39. 	B[n] = make_pair(INF,n);
  40. 	sort(B, B+n+1);
  41.  
  42. 	if(k==1) {
  43. 		cout << l << endl;
  44. 		return 0;
  45. 	}
  46.  
  47. 	for(int i=0; i<n; i++)
  48. 		num[i] = upper_bound(B,B+n+1,make_pair(B[i].F,n+1)) - B - 1;
  49.  
  50. 	int dp[n+1][k+1];
  51. 	int cum[n+1][k+1];
  52.  
  53. 	for(int i=0; i<n; i++) {
  54. 		dp[i][1] = 1;
  55. 		cum[i][1] = (i==0) ? (dp[i][1]) : (cum[i-1][1] + dp[i][1]);
  56. 		if(cum[i][1] >= MOD)
  57. 				cum[i][1] -= MOD;
  58. 	}
  59.  
  60. 	for(int i=2; i<=k; i++) {
  61. 		for(int j=0; j<n; j++) {
  62. 			dp[j][i] = cum[ num[j] ][i-1];
  63. 		}
  64. 		for(int j=0; j<n; j++) {
  65. 			cum[j][i] = (j==0) ? dp[j][i] : cum[j-1][i] + dp[j][i];
  66. 			if(cum[j][i] >= MOD)
  67. 				cum[j][i] -= MOD;
  68. 		}
  69. 	}
  70.  
  71. 	LL ans = 0;
  72. 	LL r = l%n; LL mx = l/n;
  73. 	for(int i=0; i<n; i++) {
  74. 		for(int j=1; j<=k ; j++) {
  75.  
  76. 			int val = 0; 
  77. 			if(B[i].second < r) {
  78. 				if(mx-j+1 >= 0) {
  79. 					val = (dp[i][j] * 1ll * ((mx-j+2)%MOD))%MOD;
  80. 				} 
  81. 			}
  82. 			else if(mx-j>=0) {
  83. 				val = (dp[i][j] * 1ll * ((mx-j+1)%MOD))%MOD;
  84. 			}
  85. 			ans += val;
  86. 			if(ans >= MOD)
  87. 				ans -= MOD;
  88. 		}
  89. 	}
  90.  
  91. 	cout << ans << endl;
  92.  
  93. }
Time limit exceeded #stdin #stdout 5s 18312KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/S98N8o
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!