Guest User

coincomb.java

a guest
May 16th, 2020
254
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4.  
  5. public class Main{
  6. public static void main(String[] args) {
  7. MyScanner sc = new MyScanner();
  8. out = new PrintWriter(new BufferedOutputStream(System.out));
  9.  
  10. int n = sc.nextInt();
  11. int t = sc.nextInt();
  12.  
  13. long MOD = (long)(Math.pow(10,9) + 7);
  14.  
  15. int[] coins = new int[n];
  16. long[] targets = new long[t+1];
  17.  
  18. for (int i = 0; i < n; i++){
  19. coins[i] = sc.nextInt();
  20. }
  21.  
  22.  
  23. mergeSort(coins);
  24. targets[0] = 1;
  25. for (int i = 0; i <= t; i++){
  26. if (targets[i] == 0 )continue;
  27. for (int j = 0; j < n; j++){
  28. if (i + coins[j] > t) break;
  29.  
  30. targets[i+coins[j]] += targets[i];
  31. targets[i+coins[j]] %= MOD;
  32.  
  33.  
  34. }
  35. }
  36. out.println(targets[t]);
  37.  
  38.  
  39. out.close();
  40. }
  41. static void mergeSort(int[] A){ // low to hi sort, single array only
  42. int n = A.length;
  43. if (n < 2) return;
  44. int[] l = new int[n/2];
  45. int[] r = new int[n - n/2];
  46.  
  47. for (int i = 0; i < n/2; i++){
  48. l[i] = A[i];
  49. }
  50.  
  51. for (int j = n/2; j < n; j++){
  52. r[j-n/2] = A[j];
  53. }
  54.  
  55. mergeSort(l);
  56. mergeSort(r);
  57. merge(l, r, A);
  58. }
  59.  
  60. static void merge(int[] l, int[] r, int[] a){
  61. int i = 0, j = 0, k = 0;
  62. while (i < l.length && j < r.length && k < a.length){
  63. if (l[i] < r[j]){
  64. a[k] = l[i];
  65. i++;
  66. }
  67. else{
  68. a[k] = r[j];
  69. j++;
  70. }
  71. k++;
  72. }
  73. while (i < l.length){
  74. a[k] = l[i];
  75. i++;
  76. k++;
  77. }
  78.  
  79. while (j < r.length){
  80. a[k] = r[j];
  81. j++;
  82. k++;
  83. }
  84. }
  85.  
  86.  
  87.  
  88. //-----------PrintWriter for faster output---------------------------------
  89. public static PrintWriter out;
  90.  
  91. //-----------MyScanner class for faster input----------
  92. public static class MyScanner {
  93. BufferedReader br;
  94. StringTokenizer st;
  95.  
  96. public MyScanner() {
  97. br = new BufferedReader(new InputStreamReader(System.in));
  98. }
  99.  
  100. String next() {
  101. while (st == null || !st.hasMoreElements()) {
  102. try {
  103. st = new StringTokenizer(br.readLine());
  104. } catch (IOException e) {
  105. e.printStackTrace();
  106. }
  107. }
  108. return st.nextToken();
  109. }
  110.  
  111. int nextInt() {
  112. return Integer.parseInt(next());
  113. }
  114.  
  115. long nextLong() {
  116. return Long.parseLong(next());
  117. }
  118.  
  119. double nextDouble() {
  120. return Double.parseDouble(next());
  121. }
  122.  
  123. String nextLine(){
  124. String str = "";
  125. try {
  126. str = br.readLine();
  127. } catch (IOException e) {
  128. e.printStackTrace();
  129. }
  130. return str;
  131. }
  132.  
  133. }
  134. //--------------------------------------------------------
  135. }
RAW Paste Data