quinamatics's blog

By quinamatics, history, 7 years ago, In English

Hello, I am getting WA on test case 4. I followed the editorial quite closely, so I think the issue might lie in not properly taking the modulus. Here is my WA code: import java.util.Arrays; import java.util.HashMap; import java.util.Scanner;

public class DuffInBeach {

public static void main(String[] args) {

    Scanner s = new Scanner(System.in);
    String str = s.nextLine();
    String[] strarr = str.split(" ");
    int N = Integer.parseInt(strarr[0]);
    double L = Double.parseDouble(strarr[1]);
    int K = Integer.parseInt(strarr[2]);

    long[][] dp = new long[N][K+1];
    long[] a = new long[N];
    str = s.nextLine();
    strarr = str.split(" ");
    HashMap hmap = new HashMap();
    long[] b = new long[N];
    //Index of sortings, a[p[i]]<= a[p[i+1]];
    for(int i = 0; i < N; i++){
       a[i] = Long.parseLong(strarr[i]);
       b[i] = a[i];
       hmap.put(a[i], i);
    }
    Arrays.sort(b);
    int[] p = new int[N];
    for(int i = 0; i < N; i++)
       p[i] = (int) hmap.get(b[i]);
    //# of permutations from Block 1 to Block J, for each pos I. 
    for(int i = 0; i < dp.length; i++)
       dp[i][1] = 1;

    for(int j = 2; j <= K; j++){
       for(int i = 0; i < N; i++){
         int ptr = 0;
         while(ptr < N && a[p[ptr]]<= a[i])
          dp[i][j] = (int) ((dp[i][j]+dp[p[ptr++]][j-1])%(1e9+7));
       }
    }
    Integer denom = new Integer(N);
    long c = (long) Math.ceil(L/denom.doubleValue());
    long min = Math.min(c, K);
    int x = (int) ((L-1)%(N));

    long ans = 0;
    for(int i = 0; i <= x; i++){
       for(int j = 1; j <= min; j++){
         long sum = (long) ((dp[i][j]*(c-j+1))%(1e9+7));
         ans = (long) ((ans+sum)%(1e9+7));
       }
    }
    for(int i = x+1; i < N; i++){
       for(int j = 1; j <= Math.min(c-1,K); j++){
         long sum = (long)((dp[i][j]*(c-j)%(1e9+7)));
         ans = (long)((ans+sum)%(1e9+7));
       }
    }
    System.out.println(ans);
}

}

  • Vote: I like it
  • 0
  • Vote: I do not like it