题解 | #无穷无尽的数#

F 无穷无尽的数

先以取模确定所截串结尾元素，便可将包括结尾并向前取的n个元素视作新的“循环串x”，此题便成了一道考察 快速幂，逆元和等比数列求和的问题。

（以题目所给样例举例）循环串以第三元素“1”结束，可得新串为“9810191”，而根据所给区间长度确定有57个循环节，每个循环节形似 ,将其求和即为答案的第一部分，而剩下的部分则是不足以构成循环的“头部”，长为 (记为length,此处为1)，实际大小还要再乘上,最后把两部分相加就是答案（记得取模）

from sys import stdin,setrecursionlimit
from math import inf,ceil,sqrt
from collections import Counter,deque

def q_pow(i:int,j:int,mod:int)->int:
    res=1
    while j:
        if j&1:
            res=(res*i)%mod
        i=(i*i)%mod
        j>>=1
    return res

mod=998244353

n,l,r=[int(_) for _ in stdin.readline().split()]
x=list(stdin.readline().rstrip())
lth=r-l+1

begin=(r%n+n-1)%n
y=[x[(begin-i+n)%n] for i in range(n-1,-1,-1)] #新的循环节x
num=int(''.join(y))

begin=(l%n+n-1)%n 
head=['0']+[x[(begin+i)%n] for i in range(lth%n)] #头部
head=int(''.join(head))*q_pow(10,lth-lth%n,mod)

cir=lth//n

ny=q_pow(q_pow(10,n,mod)-1,mod-2,mod) #逆元

mid=(q_pow(10,n*cir,mod)-1)*ny%mod #等比数列求和

head=(head+num*mid%mod)%mod 

print(head)

赛时没写完，AK梦破碎