fork download 
  1. import java.io.*;
  2. import java.math.BigInteger;
  3. import java.util.*;
  4. public class Main {
  5. 	 public static void main(String[] args) throws Exception {
  6. 	        InputReader in = new InputReader(System.in);
  7. 	        OutputWriter out = new OutputWriter(System.out);
  8. 			Task Solver = new Task();
  9. 			int t = in.readInt();
  10. 			while(t-- > 0)
  11. 				Solver.solve(in,out);
  12. 			out.close();
  13. 	 }
  14. }
  15. class Task{
  16. 	int n;
  17. 	String s;
  18. 	String S[] = new String[100];
  19. 	BigInteger zero = new BigInteger("0");
  20. 	BigInteger two = new BigInteger("2");
  21. 	BigInteger m;
  22. 	public void solve(InputReader in, OutputWriter out) {
  23. 		n = in.readInt();
  24. 		String t = in.readString();
  25. 		m = new BigInteger(t);
  26. 		s = in.readString();
  27. 		S[0] = "1";
  28. 		for(int i = 1; i < 100; ++i){
  29. 		    S[i] = S[i - 1] + "0"; 
  30. 		}
  31. 		out.printLine(recur(0,zero));
  32. 	}
  33. 	private long recur(int pos, BigInteger val) {
  34. 		if(pos >= s.length()) {
  35. 			if(val.mod(m).equals(zero)) {
  36. 				return 1;
  37. 			}
  38. 			else return 0;
  39. 		}
  40. 		long ret = 0;
  41. 		BigInteger new_val = val;
  42. 		if(s.charAt(s.length() - 1 - pos) != '_') {
  43. 			int num = s.charAt(s.length() - 1 - pos ) == '1' ? 1 : 0;
  44. 			if(num == 1) {
  45. 				BigInteger q = new BigInteger(S[pos],2);
  46. 				new_val = new_val.or(q);
  47. 			}
  48. 			ret += recur(pos + 1, new_val);
  49. 		}
  50. 		else {
  51. 			BigInteger q = new BigInteger(S[pos],2);
  52. 			new_val = new_val.or(q);
  53. 			ret += recur(pos + 1, new_val);
  54. 			ret += recur(pos + 1, val);
  55. 		}
  56. 		return ret;
  57. 	}
  58. }
  59. class InputReader {
  60. 	private InputStream stream;
  61. 	private byte[] buf = new byte[1024];
  62. 	private int curChar;
  63. 	private int numChars;
  64. 	private SpaceCharFilter filter;
  65. 	public InputReader(InputStream stream) {
  66. 		this.stream = stream;
  67. 	}
  68. 	public int read() {
  69. 		if (numChars == -1) {
  70. 			throw new InputMismatchException();
  71. 		}
  72. 		if (curChar >= numChars) {
  73. 			curChar = 0;
  74. 			try {
  75. 				numChars = stream.read(buf);
  76. 			} catch (IOException e) {
  77. 				throw new InputMismatchException();
  78. 			}
  79. 			if (numChars <= 0) {
  80. 				return -1;
  81. 			}
  82. 		}
  83. 		return buf[curChar++];
  84. 	}
  85. 	public int readInt() {
  86. 		int c = read();
  87. 		while (isSpaceChar(c)) {
  88. 			c = read();
  89. 		}
  90. 		int sgn = 1;
  91. 		if (c == '-') {
  92. 			sgn = -1;
  93. 			c = read();
  94. 		}
  95. 		int res = 0;
  96. 		do {
  97. 			if (c < '0' || c > '9') {
  98. 				throw new InputMismatchException();
  99. 			}
  100. 			res *= 10;
  101. 			res += c - '0';
  102. 			c = read();
  103. 		} while (!isSpaceChar(c));
  104. 		return res * sgn;
  105. 	}
  106. 	public String readString() {
  107. 		int c = read();
  108. 		while (isSpaceChar(c)) {
  109. 			c = read();
  110. 		}
  111. 		StringBuilder res = new StringBuilder();
  112. 		do {
  113. 			res.appendCodePoint(c);
  114. 			c = read();
  115. 		} while (!isSpaceChar(c));
  116. 		return res.toString();
  117. 	}
  118. 	public double readDouble() {
  119. 		int c = read();
  120. 		while (isSpaceChar(c)) {
  121. 			c = read();
  122. 		}
  123. 		int sgn = 1;
  124. 		if (c == '-') {
  125. 			sgn = -1;
  126. 			c = read();
  127. 		}
  128. 		double res = 0;
  129. 		while (!isSpaceChar(c) && c != '.') {
  130. 			if (c == 'e' || c == 'E') {
  131. 				return res * Math.pow(10, readInt());
  132. 			}
  133. 			if (c < '0' || c > '9') {
  134. 				throw new InputMismatchException();
  135. 			}
  136. 			res *= 10;
  137. 			res += c - '0';
  138. 			c = read();
  139. 		}
  140. 		if (c == '.') {
  141. 			c = read();
  142. 			double m = 1;
  143. 			while (!isSpaceChar(c)) {
  144. 				if (c == 'e' || c == 'E') {
  145. 					return res * Math.pow(10, readInt());
  146. 				}
  147. 				if (c < '0' || c > '9') {
  148. 					throw new InputMismatchException();
  149. 				}
  150. 				m /= 10;
  151. 				res += (c - '0') * m;
  152. 				c = read();
  153. 			}
  154. 		}
  155. 		return res * sgn;
  156. 	}
  157. 	public long readLong() {
  158. 		int c = read();
  159. 		while (isSpaceChar(c)) {
  160. 			c = read();
  161. 		}
  162. 		int sgn = 1;
  163. 		if (c == '-') {
  164. 			sgn = -1;
  165. 			c = read();
  166. 		}
  167. 		long res = 0;
  168. 		do {
  169. 			if (c < '0' || c > '9') {
  170. 				throw new InputMismatchException();
  171. 			}
  172. 			res *= 10;
  173. 			res += c - '0';
  174. 			c = read();
  175. 		} while (!isSpaceChar(c));
  176. 		return res * sgn;
  177. 	}
  178.  
  179. 	public boolean isSpaceChar(int c) {
  180. 		if (filter != null) {
  181. 			return filter.isSpaceChar(c);
  182. 		}
  183. 		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  184. 	}
  185. 	public String next() {
  186. 		return readString();
  187. 	}
  188.  
  189. 	public interface SpaceCharFilter {
  190. 		public boolean isSpaceChar(int ch);
  191. 	}
  192. }
  193. class OutputWriter {
  194. 	private final PrintWriter writer;
  195.  
  196. 	public OutputWriter(OutputStream outputStream) {
  197. 		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  198. 	}
  199. 	public OutputWriter(Writer writer) {
  200. 		this.writer = new PrintWriter(writer);
  201. 	}
  202. 	public void print(Object... objects) {
  203. 		for (int i = 0; i < objects.length; i++) {
  204. 			if (i != 0) {
  205. 				writer.print(' ');
  206. 			}
  207. 			writer.print(objects[i]);
  208. 		}
  209. 		writer.flush();
  210. 	}
  211. 	public void printLine(Object... objects) {
  212. 		print(objects);
  213. 		writer.println();
  214. 		writer.flush();
  215. 	}
  216. 	public void close() {
  217. 		writer.close();
  218. 	}
  219. 	public void flush() {
  220. 		writer.flush();
  221. 	}
  222. }
Success #stdin #stdout 0.1s 36332KB
comments (?)
stdin 
1
5
2
_____
stdout 
16
https://ideone.com/qBrdoq
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
secret

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!