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
stdin
Standard input is empty
stdout
Standard output is empty