fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/hCsaDO
language:
Java (12.0.1)
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!