結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー titiatitia
提出日時 2023-06-22 01:26:18
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 31 ms / 800 ms
コード長 1,506 bytes
コンパイル時間 866 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-06-29 10:03:22
合計ジャッジ時間 6,083 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 115
権限があれば一括ダウンロードができます

ソースコード

diff # 

K,L,R=map(int,input().split())

mod=10**9+7

K=min(K,64)
K-=1

MOJI=[1]
SUM=[1]
MUL=[1]
for i in range(65):
    k=(i+2)**2
    S=0
    M=1
    for s in str(k):
        if s=="0":
            S+=10
            M*=10
        else:
            S+=int(s)
            M*=int(s)
        M%=mod
    MOJI.append(MOJI[-1]*2+len(str((i+2)**2)))
    SUM.append(SUM[-1]*2+S)
    MUL.append(MUL[-1]*MUL[-1]*M%mod)

if R>MOJI[K]:
    print(-1)
    exit()

if K==0:
    print(0,0)
    exit()

def calc(K,x):
    #print("!",K,x)
    if x==0:
        return 0,1
    if MOJI[K]==x:
        return SUM[K],MUL[K]
    S=0
    M=1

    if MOJI[K-1]==x:
        return SUM[K-1],MUL[K-1]
    if MOJI[K-1]<x:
        nec=str((K+1)**2)

        S=SUM[K-1]
        M=MUL[K-1]

        x-=MOJI[K-1]

        if x<=len(nec):
            for i in range(x):
                if nec[i]=="0":
                    S+=10
                    M*=10
                else:
                    S+=int(nec[i])
                    M*=int(nec[i])

                M%=mod

            return S,M
        else:
            x-=len(nec)
            for i in range(len(nec)):
                if nec[i]=="0":
                    S+=10
                    M*=10
                else:
                    S+=int(nec[i])
                    M*=int(nec[i])

                M%=mod

            u,v=calc(K-1,x)

            return S+u,M*v%mod
    else:
        u,v=calc(K-1,x)
        return u,v

a,b=calc(K,L-1)
c,d=calc(K,R)

print(c-a,d*pow(b,mod-2,mod)%mod)
0