No.3579 Range Product Inverse Image
タグ : / 解いたユーザー数 22
作問者 : 👑
Problem Statement
You are given as input a positive integer $N$, a prime $P$, a non-negative integer $C$, and a sequence $A$ of non-negative integers of length $N$.
Find the number of pairs of integers $(\ell,r)$ satisfying $1 \leq \ell \leq r \leq N$ and
$\displaystyle \prod_{i = \ell}^{r} A_i \equiv C \pmod{P} $
.
Here, for each positive integer $i$ not exceeding $N$, $A_i$ denotes the $i$-th element of $A$. ($A = (A_1,\ldots,A_N)$)
Input
The input is given from standard input in $2$ lines in the following format:
- The $1$st line contains $N, P, C$, separated by single spaces.
- The $2$nd line contains $A_i$ for each positive integer $i$ not exceeding $N$, in increasing order of $i$, separated by single spaces.
$N$ $P$ $C$ $A_1$ $\cdots$ $A_N$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^5$.
- $P$ is a prime satisfying $1 \leq P \leq 10^9$.
- $C$ is an integer satisfying $0 \leq C < P$.
- For every positive integer $i$ not exceeding $N$, $A_i$ is an integer satisfying $0 \leq A_i < P$.
Output
Print the number of pairs of integers $(\ell,r)$ satisfying the conditions on $1$ line.
Print a newline at the end.
Sample
Sample 1
Input
1 2 0 0
Output
1
We have $(N,P,C) = (1,2,0)$ and $A = (0)$. The only pair of integers $(\ell,r)$ satisfying $1 \leq \ell \leq r \leq N$ is $(1,1)$, and
$\displaystyle \prod_{i=1}^{1} A_i = A_1 = 0 \textcolor{blue}{\equiv} C \pmod{P} $
holds.
Sample 2
Input
2 2 1 1 1
Output
3
We have $(N,P,C) = (2,2,1)$ and $A = (1,1)$. There are $3$ pairs of integers $(\ell,r)$ satisfying $1 \leq \ell \leq r \leq N$, namely $(1,1),(1,2),(2,2)$, and
$\displaystyle \begin{array}{rcccl} \displaystyle \prod_{i=1}^{1} A_i &\displaystyle = &\displaystyle A_1 &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=1}^{2} A_i &\displaystyle = &\displaystyle A_1 A_2 &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=2}^{2} A_i &\displaystyle = &\displaystyle A_2 &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \end{array} $
hold.
Sample 3
Input
2 2 0 1 0
Output
2
We have $(N,P,C) = (2,2,0)$ and $A = (1,0)$. There are $3$ pairs of integers $(\ell,r)$ satisfying $1 \leq \ell \leq r \leq N$, namely $(1,1),(1,2),(2,2)$, and
$\displaystyle \begin{array}{rcccl} \displaystyle \prod_{i=1}^{1} A_i &\displaystyle = &\displaystyle A_1 &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{red}{\not\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=1}^{2} A_i &\displaystyle = &\displaystyle A_1 A_2 &\displaystyle = &\displaystyle 0 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=2}^{2} A_i &\displaystyle = &\displaystyle A_2 &\displaystyle = &\displaystyle 0 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \end{array} $
hold.
Sample 4
Input
2 3 1 2 2
Output
1
We have $(N,P,C) = (2,3,1)$ and $A = (2,2)$. There are $3$ pairs of integers $(\ell,r)$ satisfying $1 \leq \ell \leq r \leq N$, namely $(1,1),(1,2),(2,2)$, and
$\displaystyle \begin{array}{rcccl} \displaystyle \prod_{i=1}^{1} A_i &\displaystyle = &\displaystyle A_1 &\displaystyle = &\displaystyle 2 &\displaystyle \textcolor{red}{\not\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=1}^{2} A_i &\displaystyle = &\displaystyle A_1 A_2 &\displaystyle = &\displaystyle 4 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=2}^{2} A_i &\displaystyle = &\displaystyle A_2 &\displaystyle = &\displaystyle 2 &\displaystyle \textcolor{red}{\not\equiv} &\displaystyle C \pmod{P} \end{array} $
hold.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。