結果

問題 No.2568 列辞書順列列
ユーザー navel_tosnavel_tos
提出日時 2023-12-02 16:07:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 378 ms / 3,000 ms
コード長 2,167 bytes
コンパイル時間 447 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 114,680 KB
最終ジャッジ日時 2023-12-02 16:07:29
合計ジャッジ時間 11,478 ms
ジャッジサーバーID
（参考情報） 		judge9 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
53,460 KB
testcase_01 AC 33 ms
53,460 KB
testcase_02 AC 252 ms
76,012 KB
testcase_03 AC 273 ms
76,008 KB
testcase_04 AC 344 ms
112,256 KB
testcase_05 AC 311 ms
112,256 KB
testcase_06 AC 321 ms
112,256 KB
testcase_07 AC 316 ms
112,256 KB
testcase_08 AC 346 ms
112,256 KB
testcase_09 AC 330 ms
114,680 KB
testcase_10 AC 326 ms
114,680 KB
testcase_11 AC 350 ms
114,680 KB
testcase_12 AC 337 ms
114,680 KB
testcase_13 AC 331 ms
114,680 KB
testcase_14 AC 337 ms
114,680 KB
testcase_15 AC 378 ms
114,680 KB
testcase_16 AC 333 ms
114,680 KB
testcase_17 AC 330 ms
114,680 KB
testcase_18 AC 354 ms
114,680 KB
testcase_19 AC 329 ms
114,680 KB
testcase_20 AC 321 ms
114,680 KB
testcase_21 AC 339 ms
114,680 KB
testcase_22 AC 323 ms
114,680 KB
testcase_23 AC 321 ms
114,680 KB
testcase_24 AC 320 ms
114,680 KB
testcase_25 AC 343 ms
114,680 KB
testcase_26 AC 327 ms
114,680 KB
権限があれば一括ダウンロードができます

ソースコード

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