Weighted Necklace

All submissions for this problem are available.
You are given $K$ different colors of beads. A bead of the $i$th color has a weight $w_i$. You have infinitely many beads of each color. All the beads of the same color have the same weight. You have to answer $q$ independent queries. For each query, you will be given $S$. You have to form a necklace consisting of $n$ beads such that the total weight of the necklace is $S$. You can use any number of beads of a single color (possibly zero). Count the number of distinct possible necklaces you can make. Two necklaces will be considered the same if one can be rotated to another. ### Input  First line contains $n$, denoting the size of the necklace.  Second line contains $K$, denoting the number of different colors.  Third line contains $K$ space separated integers, where the $i$th integer $w_i$ denotes the weight of a bead of color $i$.  Fourth line contains $q$, denoting the number of queries.  Each of the next $q$ lines will contain a single integer $S$, denoting the total weight of the necklace for this query. ### Output For each query, output in a new line, the number of valid necklaces mod $998244353$. ### Constraints  $1 \le n, q, K, w_i, S \le 10^5$  $n$ will be a power of two ### Example Input ``` 4 4 1 2 3 4 4 5 6 7 8 ``` ### Example Output ``` 1 3 5 9 ``` ### Explanation For S = 6, three ways to form the necklace are:  1 > 1 > 1 > 3  1 > 1 > 2 > 2  1 > 2 > 1 > 2 Please note, we do not count 2 > 1 > 1 > 2 because it is just a rotation of 1 > 1 > 2 > 2.Author:  msi_cse_buet 
Tags  msi_cse_buet 
Date Added:  5122019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 