$\binom{n}{r}$与$\binom{n}{r-1}$之间相差$n-r+1/r$，而对$1$到$x$之间的$B$而言有$S_B(xp^a)=S_B(x)p^a$，因此本题需要频繁在一些区间上更新并求和，从而可以用线段树来实现，最终结果是$852950321$。
注：因使用sympy求乘法逆以及分解质因数，以下代码为Python 3。
import sympy
N=11111111
mod=10**9+993
primes=[1]+[*sympy.sieve.primerange(N+1)]
d={p:(i,sympy.mod_inverse(p,mod)) for i,p in enumerate(primes)}
primes.append(N+1)
def f(a,b):
if a+1==b:
return [primes[a+1]-primes[a],1,[],[]]
c=(a+b)//2
u=f(a,c)
v=f(c,b)
return [u[0]+v[0],1,u,v]
def cal(t,target,v,a,b):
if b<=target:
t[0]=(t[0]*v)%mod
t[1]=(t[1]*v)%mod
return
c=(a+b)//2
cal(t[2],target,v,a,c)
if target>c:
cal(t[3],target,v,c,b)
t[0]=t[1]*(t[2][0]+t[3][0])%mod
res=N
t=f(0,len(d))
x=1
for i in range(N//2):
x=x*(N-i)*sympy.mod_inverse(i+1,mod)%mod
for p,c in sympy.factorint(N-i).items():
cal(t,d[p][0],pow(d[p][1],c,mod),0,len(d))
for p,c in sympy.factorint(i+1).items():
cal(t,d[p][0],pow(p,c,mod),0,len(d))
res+=t[0]*x
print(2*res%mod)
|
