結果
問題 | No.313 π |
ユーザー |
|
提出日時 | 2023-11-09 10:14:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,034 ms / 5,000 ms |
コード長 | 1,708 bytes |
コンパイル時間 | 314 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 91,648 KB |
最終ジャッジ日時 | 2024-09-26 00:04:44 |
合計ジャッジ時間 | 21,624 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
from collections import *from itertools import *from functools import *from heapq import *import sys,math# input = sys.stdin.readlineT = 165858069class Rolling_hash():def __init__(self,S,mod_list = [1000000009,998244353,3000012541],base_num_list=[500009,500029,500041]):self.n = len(mod_list)self.S = Sself.N = len(self.S)self.H = [[0]*(self.N+1) for _ in range(self.n)]self.b_inv = [[1]*self.N for _ in range(self.n)]self.mod_list = mod_listfor j in range(self.n):tb = base_num_list[j]base_num = base_num_list[j]mod = mod_list[j]tb_inv = 1base_inv = pow(base_num,mod-2,mod)tH = self.S[0]self.H[j][1] = tHfor i in range(self.N-1):tH = (tH + self.S[i+1]*tb)%modself.H[j][i+2] = tHtb = (tb*base_num)%modtb_inv *= base_invtb_inv %= modself.b_inv[j][i+1] = tb_invdef query(self,j,l,r):if l>=r:return 0if l>=self.N:return 0tmp = (self.H[j][r]-self.H[j][l])*self.b_inv[j][l]%self.mod_list[j]return tmpX = input()X = X.replace('.','')X = list(X)X = [int(i) for i in X]rh = Rolling_hash(X)M = 200001mod = 10**9 + 9b = 500009for i in range(M):L = rh.query(0,0,i)R = (rh.query(0,i+1,M)*pow(b,i+1,mod))%modfor j in range(10):val = (L + j*pow(b,i,mod) + R)%modif val==T:print(X[i],j)exit()