fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  7. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  8. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  9. #define rep(i, c) for(auto &(i) : (c))
  10. #define x first
  11. #define y second
  12. #define pb push_back
  13. #define PB pop_back()
  14. #define iOS ios_base::sync_with_stdio(false)
  15. #define sqr(a) (((a) * (a)))
  16. #define all(a) a.begin() , a.end()
  17. #define error(x) cerr << #x << " = " << (x) <<endl
  18. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  19. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  20. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  21. #define L(x) ((x)<<1)
  22. #define R(x) (((x)<<1)+1)
  23. #define umap unordered_map
  24. #define double long double
  25. typedef long long ll;
  26. typedef pair<int,int>pii;
  27. typedef vector<int> vi;
  28. typedef complex<double> point;
  29. template <typename T> using os =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  30. template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
  31. template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}
  32. const int maxn = 1e6 + 100, mod = 1e9 + 7;
  33. int a[maxn], dp[maxn][2], p[maxn];
  34. ll l, c;
  35. int n, k;
  36. ll ans;
  37. int last;
  38. inline void calc(int i, int j){
  39. 	ll t = (c - j + 1LL) % mod;
  40. 	if(i > last && l % (ll)n)
  41. 		t = (t - 1LL + mod) % mod;
  42. 	ll x = (1LL * t * (ll)dp[i][j & 1]) % mod;
  43. 	ans = (ans + x) % mod;
  44. }
  45. int main(){
  46. 	scanf("%d %lld %d", &n, &l, &k);
  47. 	c = l / (ll)n;
  48. 	last = ((ll)(l - 1LL) % (ll)n);
  49. 	if(l % n)
  50. 		++ c;
  51. 	k = (int)min((ll)k, c);
  52. 	For(i,0,n){
  53. 		scanf("%d", a + i);
  54. 		p[i] = i;
  55. 		dp[i][1] = 1;
  56. 		calc(i, 1);
  57. 	}
  58. 	sort(p, p + n, [](const int &i, const int &j){return pii(a[i], i) < pii(a[j], j);});
  59. 	int po = 0;
  60. 	For(j,2,k + 1){
  61. 		po = 0;
  62. 		int x = j & 1, y = !x;
  63. 		int sum = 0;
  64. 		For(iii,0,n){
  65. 			int i = p[iii];
  66. 			while(po < n && a[p[po]] <= a[i])
  67. 				sum = (sum + dp[p[po ++]][y]) % mod;
  68. 			dp[i][x] = sum;
  69. 			calc(i, j);
  70. 		}
  71. 	}
  72. 	ans %= mod;
  73. 	ans = (ans + mod) % mod;
  74. 	printf("%d\n", (int)ans);
  75. 	return 0;
  76. }
Runtime error #stdin #stdout 0s 19040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7QJJHJ
language:
C++14 (gcc 8.3)
created:
9 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!