No.3579 区間積逆像
p-adic問題文
入力に正整数 $N$ と素数 $P$ と 非負整数 $C$ と、長さ $N$ の非負整数列 $A$ が与えられます。
$1 \leq \ell \leq r \leq N$ かつ
$\displaystyle \prod_{i = \ell}^{r} A_i \equiv C \pmod{P} $
を満たす整数の組 $(\ell,r)$ の個数を求めてください。
ただし $N$ 以下の各正整数 $i$ に対し、$A_i$ は $A$ の $i$ 個目の成分を表します。（$A = (A_1,\ldots,A_N)$）
入力
入力は以下の形式で標準入力から $2$ 行で与えられます：
- $1$ 行目に $N, P, C$ が半角空白区切りで与えられます。
- $2$ 行目に $N$ 以下の各正整数 $i$ に対する $A_i$ が $i$ の小さい順に半角空白区切りで与えられます。
$N$ $P$ $C$ $A_1$ $\cdots$ $A_N$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^5$ を満たす整数である。
- $P$ は $1 \leq P \leq 10^9$ を満たす素数である。
- $C$ は $0 \leq C < P$ を満たす整数である。
- $N$ 以下の任意の正整数 $i$ に対し、$A_i$ は $0 \leq A_i < P$ を満たす整数である。
出力
条件を満たす整数の組 $(\ell,r)$ の個数を $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 2 0 0
出力
1
$(N,P,C) = (1,2,0)$ で $A = (0)$ です。$1 \leq \ell \leq r \leq N$ を満たす整数の組 $(\ell,r)$ は $(1,1)$ のみであり、
$\displaystyle \prod_{i=1}^{1} A_i = A_1 = 0 \textcolor{blue}{\equiv} C \pmod{P} $
です。
サンプル2
入力
2 2 1 1 1
出力
3
$(N,P,C) = (2,2,1)$ で $A = (1,1)$ です。$1 \leq \ell \leq r \leq N$ を満たす整数の組 $(\ell,r)$ は $(1,1),(1,2),(2,2)$ の $3$ 個あり、
$\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} $
です。
サンプル3
入力
2 2 0 1 0
出力
2
$(N,P,C) = (2,2,0)$ で $A = (1,0)$ です。$1 \leq \ell \leq r \leq N$ を満たす整数の組 $(\ell,r)$ は $(1,1),(1,2),(2,2)$ の $3$ 個あり、
$\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} $
です。
サンプル4
入力
2 3 1 2 2
出力
1
$(N,P,C) = (2,3,1)$ で $A = (2,2)$ です。$1 \leq \ell \leq r \leq N$ を満たす整数の組 $(\ell,r)$ は $(1,1),(1,2),(2,2)$ の $3$ 個あり、
$\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} $
です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。