fork download
  1. import java.io.*;
  2. import java.util.Arrays;
  3. import java.util.Comparator;
  4. import java.util.Locale;
  5. import java.util.StringTokenizer;
  6.  
  7. public class TaskB {
  8. private final InputReader reader;
  9. private final OutputWriter writer;
  10.  
  11. public TaskB(InputReader reader, OutputWriter writer) {
  12. this.reader = reader;
  13. this.writer = writer;
  14. }
  15.  
  16. public static void main(String[] args) {
  17. InputReader reader = new InputReader(System.in);
  18. OutputWriter writer = new OutputWriter(System.out);
  19. new TaskB(reader, writer).run();
  20. writer.writer.flush();
  21. }
  22.  
  23. public void run() {
  24. final int n = reader.nextInt();
  25. long len = reader.nextLong();
  26. int k = reader.nextInt();
  27. int[][] D = new int[k][n];
  28. for (int i = 0; i < n; i++) {
  29. D[0][i] = (i < len) ? 1 : 0;
  30. }
  31. Integer[] order = new Integer[n];
  32. for (int i = 0; i < n; i++)
  33. order[i] = i;
  34. final int[] A = new int[n];
  35. for (int i = 0; i < n; i++)
  36. A[i] = reader.nextInt();
  37. Arrays.sort(order, new Comparator<Integer>() {
  38. @Override
  39. public int compare(Integer a, Integer b) {
  40. return Integer.compare(A[a], A[b]);
  41. }
  42. });
  43.  
  44. final int MOD = 1000 * 1000 * 1000 + 7;
  45.  
  46. for (int i = 1; i < k; i++) {
  47. int sum = 0;
  48. for (int l = 0, r = 0; l < n; l = r) {
  49. while (r != n && A[order[l]] == A[order[r]])
  50. r++;
  51. for (int j = l; j < r; j++)
  52. sum = (sum + D[i - 1][order[j]] >= MOD) ? sum + D[i - 1][order[j]] - MOD : sum + D[i - 1][order[j]];
  53. for (int j = l; j < r; j++)
  54. D[i][order[j]] = sum;
  55. }
  56. }
  57.  
  58. int ans = 0;
  59. for (int i = 0; i < k; i++)
  60. for (int j = 0; j < n; j++) {
  61. if (i * n + j >= len)
  62. continue;
  63. int val = (int)((len / n + 1 - i - ((j >= len % n) ? 1 : 0)) % MOD);
  64. val = (int)((((long)val) * D[i][j]) % MOD);
  65. ans = (ans + val >= MOD) ? ans + val - MOD : ans + val;
  66. }
  67. writer.printf("%d\n", ans);
  68. }
  69.  
  70.  
  71. static class InputReader {
  72. public BufferedReader reader;
  73. public StringTokenizer tokenizer;
  74.  
  75. public InputReader(InputStream stream) {
  76. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  77. tokenizer = null;
  78. }
  79.  
  80. public String next() {
  81. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  82. try {
  83. tokenizer = new StringTokenizer(reader.readLine());
  84. } catch (IOException e) {
  85. throw new RuntimeException(e);
  86. }
  87. }
  88. return tokenizer.nextToken();
  89. }
  90.  
  91. public int nextInt() {
  92. return Integer.parseInt(next());
  93. }
  94.  
  95. public double nextDouble() {
  96. return Double.parseDouble(next());
  97. }
  98.  
  99. public long nextLong() {
  100. return Long.parseLong(next());
  101. }
  102. }
  103.  
  104. static class OutputWriter {
  105. public PrintWriter writer;
  106.  
  107. OutputWriter(OutputStream stream) {
  108. writer = new PrintWriter(stream);
  109. }
  110.  
  111. public void printf(String format, Object... args) {
  112. writer.print(String.format(Locale.ENGLISH, format, args));
  113. }
  114. }
  115. }
  116.  
  117.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
Main.java:7: error: class TaskB is public, should be declared in a file named TaskB.java
public class TaskB {
       ^
1 error
stdout
Standard output is empty