SOLVE

LATER

Nimxor and Bit-Strings

Problem

Editorial

Analytics

Given a bit-string $$str$$ of $$0s$$ and $$1s$$. you need to answer the following $$q$$ queries.

Each query will contain an integer value $$n$$. You are required to calculate how many bit-strings smaller than or equal to $$str$$ are there which are divisible by $$n$$ when converted to their decimal representation.

$$Input:$$

First line of input contains a single integer $$N$$ representing the length of string.

First line of the input contains a bit-string $$str$$ .

Second line contains a single integer $$q$$, representing the number of queries.

Next $$q$$ lines contain an integer $$n$$ .

$$Output:$$

For each of the query output the number of bit-strings smaller than or equal to $$str$$ which are divisible by $$n$$ . As the answer can be large take modulo with $$10^9+7$$.

$$Input :$$

$$1 \le N \le 10^4$$

$$ 1 \le q \le 10^5 $$

$$ 1 \le n \le 10^2 $$

Explanation

For first query n is 3. Bit-strings divisible by 3 are 1100,1001,0110,0011,0000 .

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

{"52e2784": "/pagelets/recommended-problems/algorithm/nimxor-and-bit-strings/", "52e2742": "/pagelets/suggested-problems/algorithm/nimxor-and-bit-strings/", "52e276f": "/pagelets/problems-hint/algorithm/nimxor-and-bit-strings/", "52e271b": "/pagelets/show-submission/algorithm/nimxor-and-bit-strings/", "52e275a": "/pagelets/problem-author-tester/algorithm/nimxor-and-bit-strings/"}

{}

realtime.hackerearth.com

80

61c183e4d2c9ec209422b12a89e0adf70d63c724

58a29e5cae2309f04b28

/realtime/pusher/auth/