Random Number Generator

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME77/hindi/RNG97.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME77/bengali/RNG97.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME77/mandarin/RNG97.pdf), [Russian](http://www.codechef.com/download/translated/LTIME77/russian/RNG97.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME77/vietnamese/RNG97.pdf) as well. Almir has a multiset $S = \{s_1, s_2, \ldots, s_N\}$; recall that a multiset may contain duplicate elements. At the time $t = 0$, Almir starts his random number generator and feeds his multiset to it. During each subsequent second, the random number generator would transform the multiset in the following manner:  for each valid $t$, let $S_{t1}$ be the multiset at the beginning of the $t$th second ($S_0 = S$)  for each element $x \in S_{t1}$, during the $t$th second, $x$ is transformed into $x^{random(1, K)} \, \% \, M$, where $random(1, K)$ denotes a uniformly randomly generated integer between $1$ and $K$ inclusive  at the end of the $t$th second, $S_t$ is the multiset of these transformed elements In addition, Almir can insert elements into the multiset at the end of some seconds (i.e. immediately after some transformation has finished). You should answer $Q$ queries of two types:  `1 t x`: find the expected number of elements of the multiset at the end of the $t$th second (the multiset $S_t$) that are equal to $x$  `2 t x`: insert a new element $x$ into the multiset at the end of the $t$th second (the multiset $S_t$) Note that the queries are given in chronological order and there are no overlaps between any queries or transformations. Your task is to find the answers to all queries of the first type. It can be shown that in each of these queries, the expected value can be expressed as an irreducible fraction $\frac{P}{Q}$, where $P$ and $Q$ are nonnegative integers and $Q$ is coprime to $10^9+7$. You should find $P \cdot Q^{1}$ modulo $10^9+7$, where $Q^{1}$ denotes the multiplicative inverse of $Q$ modulo $10^9+7$. ### Input  The first line of the input contains four spaceseparated integers $N$, $Q$, $K$ and $M$.  The second line contains $N$ spaceseparated integers $s_1, s_2, \ldots, s_N$.  The following $Q$ lines describe queries. For each valid $i$, the $i$th of these lines contains three spaceseparated numbers $type_i$, $t_i$ and $x_i$ describing the $i$th query. ### Output For each query of the first type, print a single line containing one integer $P \cdot Q^{1} \, \% \, (10^9+7)$. ### Constraints  $1 \le N \le 10^5$  $1 \le Q \le 10^6$  $1 \le K \le 10^9$  $1 \le M \le 100$  $M$ is a prime  $1 \le t_1 \lt t_2 \lt \ldots \lt t_Q \le 10^6$  $1 \le s_i \lt M$ for each valid $i$  $type_i \in \{1, 2\}$ for each valid $i$  $1 \le x_i \lt M$ for each valid $i$ ### Subtasks **Subtask #1 (15 points):** $1 \le Q \le 1000$ **Subtask #2 (35 points):** the only query of the first type is the last query **Subtask #3 (50 points):** original constraints ### Example Input 1 ``` 4 6 10 5 1 2 3 4 2 10 1 2 15 2 2 17 4 2 20 2 2 30 3 1 40 4 ``` ### Example Output 1 ``` 645425103 ``` ### Example Input 2 ``` 4 6 10 5 1 2 3 4 2 10 1 1 15 2 2 17 4 1 20 2 2 30 3 1 40 4 ``` ### Example Output 2 ``` 970977790 467843059 655757002 ```Author:  jafarbadour 
Editorial  https://discuss.codechef.com/problems/RNG97 
Tags  expectedvalue, jafarbadour, jafarbadour, ltime77, probability 
Date Added:  24102019 
Time Limit:  4 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. 