結果
問題 | No.493 とても長い数列と文字列(Long Long Sequence and a String) |
ユーザー |
|
提出日時 | 2021-09-26 23:34:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,386 bytes |
コンパイル時間 | 225 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 76,800 KB |
最終ジャッジ日時 | 2024-07-05 16:58:37 |
合計ジャッジ時間 | 11,203 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 115 |
ソースコード
import sysinput = lambda : sys.stdin.readline().rstrip()write = lambda x: sys.stdout.write(x+"\n")debug = lambda x: sys.stderr.write(x+"\n")writef = lambda x: print("{:.12f}".format(x))k,l,r = list(map(int, input().split()))M = 10**9+7def _sub(t):t = int(t)if t==0:t = 10return tdef sub(l):if l==0:return 0, 1ss = [1]ll = [1]pp = [1]v = 2while 1:tmp = str(v*v)if len(tmp)+ss[-1]>=l:l0 = ll[-1]p0 = pp[-1]for i in range(l-ss[-1]):l0 += _sub(tmp[i])p0 *= _sub(tmp[i])p0 %= Mreturn l0,p0ns = ss[-1]*2 + len(tmp)if ns>l:ll[-1] += sum((_sub(t) for t in tmp))p = 1for t in tmp:p *= _sub(t)p %= Mpp[-1] *= ppp[-1] %= Ml0,p0 = sub(l-ss[-1]-len(tmp))return l0+ll[-1], p0*pp[-1]%Mss.append(ns)ll.append(ll[-1]*2 + sum((_sub(t) for t in tmp)))p = 1for t in tmp:p *= _sub(t)p %= Mpp.append(pp[-1]**2 % M * p)v += 1if v>k:return None, Nonel0,p0 = sub(l-1)l1,p1 = sub(r)if l0 is None or l1 is None:print(-1)else:print(l1-l0, p1*pow(p0, M-2, M)%M)