NOI '19 P5 - Landlords

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Kevin is playing cards and now he needs to shuffle cards m times. Now let's describe the rule of the i^{th} shuffle.

For the i^{th} shuffle:

  1. Kevin will take out A_i cards from the top and make it a new pile. Now there are two piles of cards. One is the original top A_i cards and the other is the rest n-A_i cards. The relative order in these two piles remains unchanged. Note that when A_i is n or 0, there is one pile which has no card at all.

  2. Now let's merge those two piles of cards into a new pile. Suppose the first pile has X cards and the second piles has Y cards. With probability \frac{X}{X+Y}, we select the bottom card of the first pile and put the selected card to the top of the new pile. Then, with probability \frac{Y}{X+Y}, we select the bottom card of the second pile and then put the selected card to the top of the new pile.

  3. Repeat 2 until both piles are empty.

Now we have Q questions for you. You have to tell us after m times of shuffles, what's the expected score of some specific positions' card. Note that for card i, let's denote its score as f(i). In this problem, f(i) equals to either i or i^2.

Input Specification

The first line contains three integers n,m,type. When type = 1, f(i)=i. When type = 2, f(i)=i^2.

The following line contains m integers A_1\ldots A_m.

The following line contains an integer Q.

In the following Q lines, each line contains an integer c_i(1 \leq c_i \leq n), indicating that Kevin wants to know the expected score of the c_i position from top.


For all test cases, 3 \leq n \leq 10^7,1 \leq m,Q \leq 5 \times 10^5,0 \leq A_i \leq n, type \in [1,2].

Test CasenmTypeAdditional Constraints
1\le 10\le 11None
2\le 80\le 80
4\le 100\le 5\times 10^5All A_i are equal
5\le 10^71None

Output Specification

For each query, output a single integer on a single line as the answer. If the answer is \frac{A}{B}, please print C(0\leq C<998\,244\,353) where A\equiv C\times B\pmod{998\,244\,353}.

Sample Input 1

4 1 1

Sample Output 1



There are no comments at the moment.