Advertisement
Guest User

Untitled

a guest
Feb 21st, 2022
203
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.68 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. public class D {
  4. // @formatter:off
  5. static long mod=(int)(1e9)+7;
  6. static FastScanner in;
  7. static class FastScanner{
  8. private InputStream stream;
  9. private byte[] buf = new byte[1 << 16];
  10. private int curChar;
  11. private int numChars;
  12.  
  13. // standard input
  14. public FastScanner() { this(System.in); }
  15.  
  16. public FastScanner(InputStream i) {
  17. stream = i;
  18. }
  19.  
  20. // file input
  21. public FastScanner(String i) throws IOException {
  22. stream = new FileInputStream(i);
  23. }
  24.  
  25. // throws InputMismatchException() if previously detected end of file
  26. private int nextByte() {
  27. if (numChars == -1) {
  28. throw new InputMismatchException();
  29. }
  30. if (curChar >= numChars) {
  31. curChar = 0;
  32. try {
  33. numChars = stream.read(buf);
  34. } catch (IOException e) {
  35. throw new InputMismatchException();
  36. }
  37. if (numChars == -1) {
  38. return -1; // end of file
  39. }
  40. }
  41. return buf[curChar++];
  42. }
  43.  
  44. // to read in entire lines, replace c <= ' '
  45. // with a function that checks whether c is a line break
  46. public String next() {
  47. int c;
  48. do {
  49. c = nextByte();
  50. } while (c <= ' ');
  51.  
  52. StringBuilder res = new StringBuilder();
  53. do {
  54. res.appendCodePoint(c);
  55. c = nextByte();
  56. } while (c > ' ');
  57. return res.toString();
  58. }
  59.  
  60. public int nextInt() { // nextLong() would be implemented similarly
  61. int c;
  62. do {
  63. c = nextByte();
  64. } while (c <= ' ');
  65.  
  66. int sgn = 1;
  67. if (c == '-') {
  68. sgn = -1;
  69. c = nextByte();
  70. }
  71.  
  72. int res = 0;
  73. do {
  74. if (c < '0' || c > '9') {
  75. throw new InputMismatchException();
  76. }
  77. res = 10 * res + c - '0';
  78. c = nextByte();
  79. } while (c > ' ');
  80. return res * sgn;
  81. }
  82.  
  83. public long nextLong() {
  84. int c;
  85. do {
  86. c = nextByte();
  87. } while (c <= ' ');
  88.  
  89. int sgn = 1;
  90. if (c == '-') {
  91. sgn = -1;
  92. c = nextByte();
  93. }
  94.  
  95. long res = 0;
  96. do {
  97. if (c < '0' || c > '9') {
  98. throw new InputMismatchException();
  99. }
  100. res = 10 * res + c - '0';
  101. c = nextByte();
  102. } while (c > ' ');
  103. return res * sgn;
  104. }
  105. public double nextDouble() { return Double.parseDouble(next()); }
  106. }
  107. static void setIO() {try {in=new FastScanner("test.in");}catch(Exception e) {in=new FastScanner(System.in);}}// @formatter:on
  108. public static void main(String[] args) {
  109. setIO();
  110. int n=in.nextInt(),p=in.nextInt();
  111. int[]a=new int[n];
  112. for(int i=0;i<n;i++)a[i]=in.nextInt();
  113. Arrays.sort(a);
  114. Map<Integer, Integer>cmp=new HashMap<>();
  115. int c=0;
  116. for(int i=n-1;i>=0;i--) {
  117. if(cmp.containsKey(a[i])) continue;
  118. dfs(a[i],cmp,c++);
  119. }
  120. List<Integer>starting=new ArrayList<>();
  121. boolean[]v=new boolean[n];
  122. for(int i=0;i<n;i++) {
  123. int comp=cmp.get(a[i]);
  124. if(v[comp]) continue;
  125. starting.add(a[i]);
  126. v[comp]=true;
  127. }
  128. // System.out.println(cmp);
  129. // System.out.println(starting);
  130. Long[]dp=new Long[p]; // up to p
  131. solve(0,dp);
  132. long ret=0;
  133. for(int start:starting) {
  134. int log=log2(start);
  135. if(log>=p) continue;
  136. ret+=dp[log];
  137. ret%=mod;
  138. }
  139. System.out.println(ret);
  140. }
  141. static void dfs(int curr, Map<Integer, Integer>cmp,int c) {
  142. if(curr<=0) return;
  143. cmp.put(curr, c);
  144. if(curr%2==1) dfs(curr/2,cmp,c);
  145. else if(curr%4==0) dfs(curr/4,cmp,c);
  146. }
  147.  
  148. static int log2(int a) {
  149. int ret=0;
  150. while(a>1) {
  151. a/=2;
  152. ret++;
  153. }
  154. return ret;
  155. }
  156. static long solve(int curr, Long[]dp) {
  157. if(curr>=dp.length) return 0;
  158. if(curr==dp.length-1) return dp[curr]=1l;
  159. if(curr==dp.length-2) return dp[curr]=2l;
  160. if(dp[curr]!=null) return dp[curr];
  161. dp[curr]=(1+solve(curr+1,dp)+solve(curr+2,dp))%mod;
  162. return dp[curr];
  163. }
  164. }
  165.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement