h832. 次方區間問題
標籤 :
通過比率 : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-08 22:00

內容

給你一個正整數 $n$ 和一個正整數 $q$,代表有 $n$ 個數字$a_1, a_2, ..., a_n$和 $q$ 組詢問,每組詢問有一個區間 $[l, r]$ ,每次要你回答  $a_l^{{a_{l+1}}^{...^{a_r}}} \text{mod }m$

輸入說明

第一行有兩個正整數 $n, m(1\le n\le 10^5, 1\le m\le 10^9)$,然後第二行有 $n$ 個數字 $a_1,a_2,...,a_n$其中$a_i(1\le a_i\le10^9,1\le i\le n)$ ,第三行有一個正整數 $q(1\le q\le 10^5)$ 表示有 $q$ 組詢問,接下來有 $q$ 行,每行有兩個正整數$l,r(1\le l\le r\le n)$代表詢問。

輸出說明

輸出 $q$ 行,代表每個詢問的答案。

範例輸入 #1
11 998244353
10 16 4 8 7 6 3 7 4 1 4
5
3 6
4 7
2 9
3 5
1 6
範例輸出 #1
346033774
595427088
480750826
820873187
395868439
測資資訊:
記憶體限制: 256 MB
不公開 測資點#0 (10%): 2.0s , <1M
不公開 測資點#1 (10%): 2.0s , <1M
不公開 測資點#2 (10%): 2.0s , <1M
不公開 測資點#3 (10%): 2.0s , <1M
不公開 測資點#4 (10%): 2.0s , <1M
不公開 測資點#5 (10%): 2.0s , <10M
不公開 測資點#6 (10%): 2.0s , <1M
不公開 測資點#7 (10%): 2.0s , <10M
不公開 測資點#8 (10%): 2.0s , <10M
不公開 測資點#9 (10%): 2.0s , <1M
提示 :

$a^{b^c} = a^{(b^c)}$

$m$ 不一定是質數
$50\%$ 的測資 $n,q\le 1000$

$100\%$ 的測資 沒有特別限制

標籤:
出處:
CF 907F [管理者: Easonsfriend (去寫./Problems?ow...) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」