結果

問題 No.2568 列辞書順列列
コンテスト
ユーザー navel_tos
提出日時 2023-12-02 16:07:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 404 ms / 3,000 ms
コード長 2,167 bytes
コンパイル時間 522 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 115,200 KB
最終ジャッジ日時 2024-09-26 19:51:50
合計ジャッジ時間 12,543 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#緑以下L

#Rolling Hash: 2^61-1 の原始根: r=37  基数はM-1と互いに素、かつ r^k(mod M)>max(A)を推奨
class Rolling_Hash:
    def __init__(self,Base=128,MOD=2**61-1): self._B=Base; self._MOD=MOD; self._Bf=[1]
    def _translate(self,String):
        return [ord(String[i]) for i in range(len(String))] if isinstance(String,str) else String
    def _factorial(self,N):  #B^iを前計算する
        Start=len(self._Bf)
        while len(self._Bf)<=N: self._Bf+=[0]*len(self._Bf)
        for i in range(Start,len(self._Bf)): self._Bf[i]=self._Bf[i-1]*self._B%self._MOD
    def hash(self,Sequence):
        if isinstance(Sequence,str): Sequence=self._translate(Sequence)
        self._factorial(len(Sequence))
        return sum(Sequence[i]*self._Bf[len(Sequence)-i-1]%self._MOD
                   for i in range(len(Sequence)))%self._MOD
    def rolling(self,Sequence,Len):
        if isinstance(Sequence,str): Sequence=self._translate(Sequence)
        if len(Sequence)<=Len: return [self.hash(Sequence)]
        L=[0]*(len(Sequence)-Len+1); L[0]=self.hash(Sequence[:Len])
        for i in range(len(Sequence)-Len):
            L[i+1]=L[i]*self._B-Sequence[i]*self._Bf[Len]+Sequence[i+Len]
            if L[i+1]>=self._MOD: L[i+1]%=self._MOD
        return L

    #ここからQuick Rolling Hash  文字列前登録の元、O(1)でハッシュ値を返す
    def build(self,Sequence):  #文字列を受入れ
        if isinstance(Sequence,str): Sequence=self._translate(Sequence)
        self._S=Sequence; self._N=len(self._S); self._factorial(self._N); self._H=[0]*(self._N+1)
        for i in range(self._N): self._H[i]=(self._H[i-1]*self._B+self._S[i])%self._MOD
        return
    def Qhash(self,L,R):  #S[L,R)のハッシュ値を返す
        return (self._H[R-1]-self._H[L-1]*self._Bf[R-L])%self._MOD if L<R<=self._N else 0
        

#入力受取
N,M,Q = map(int,input().split())
A = list(map(int,input().split()))
MOD = 998244353

#Rolling Hashの実験
B = [i-1 for i in A]
RH = Rolling_Hash(M,MOD)
RH.build(B)

#クエリを処理
for _ in range(Q):
    L,R = map(int,input().split())
    cnt = RH.Qhash(L-1,R)+1
    print(cnt % MOD)
0