All Tracks Math Number Theory Basic Number Theory-1 Problem

Mancunian And Multiplicative Queries
Tag(s):

Medium, Sqrt-Decomposition

Problem
Editorial
Analytics

Mancunian is in a hurry! He is late for his date with Nancy. So he has no time to deal with a long and complex problem statement.
You are given two arrays, $$A$$ and $$FUNC$$. Each element of either array, $$A_i$$ or $$FUNC_i$$, is a positive integer not greater than $$C$$. Given $$Q$$ queries, each of the form $$L$$ $$R$$, the answer for each query is \begin{equation} \prod_{i=1}^{C} FUNC[cnt_i] \end{equation} where $$cnt_i$$ is the frequency of the integer $$i$$ in the range $$L$$ $$R$$.
The answer to the problem is the product of the answers of all the individual queries modulo $$10^9+7$$.

Input format

The first line contains three integers $$N$$, $$C$$ and $$Q$$ denoting the size of the array, the range of allowed values for each array element and the number of queries respectively.
The second line contains $$N$$ positive integers, denoting the elements of the array $$A$$. The $$ith$$ (1-indexed) of these represents $$A_i$$.
The third line contains $$N+1$$ positive integers, denoting the elements of the array $$FUNC$$. The $$ith$$ (0-indexed) of these represents $$FUNC_i$$.
The $$ith$$ of the next $$Q$$ lines contains two integers, $$L$$ and $$R$$ for the $$ith$$ query.

Output format

Print a single integer, which is the answer to the given problem.

Constraints

  • $$1 \le N, Q \le 50,000$$
  • $$1 \le C \le 1,000,000$$
  • $$1 \le L \le R \le N$$
SAMPLE INPUT
5 5 3
1 2 2 3 3
1 1 2 3 4 5
2 4
1 2
4 5
SAMPLE OUTPUT
4
Explanation

In the range specified by the first query, there are 0 occurrences of $$1$$, 2 occurrences of $$2$$, 1 occurrence of $$3$$ and 0 occurrences of both $$4$$ and $$5$$. So the answer for the first query is $$FUNC[0]$$ * $$FUNC[2]$$ * $$FUNC[1]$$ * $$FUNC[0]$$ * $$FUNC[0]$$ $$=$$ $$2$$.

In the range specified by the second query, there is 1 occurrence of $$1$$, 1 occurrence of $$2$$, 0 occurrences of $$3$$ and 0 occurrences of both $$4$$ and $$5$$. So the answer for the second query is $$FUNC[1]$$ * $$FUNC[1]$$ * $$FUNC[0]$$ * $$FUNC[0]$$ * $$FUNC[0]$$ $$=$$ $$1$$.

In the range specified by the third query, there are 0 occurrences of $$1$$, 0 occurrences of $$2$$, 2 occurrences of $$3$$ and 0 occurrences of both $$4$$ and $$5$$. So the answer for the third query is $$FUNC[0]$$ * $$FUNC[0]$$ * $$FUNC[2]$$ * $$FUNC[0]$$ * $$FUNC[0]$$ $$=$$ $$2$$.

Hence the final answer is $$2$$ * $$1$$ * $$2$$ $$=$$ $$4$$.

Time Limit: 5.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, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications