注意本题的模数是而不是OI比赛中常见的！
依次记录连续出现的数的次数，如此可得一新序列，例如题面例子中对应的新序列是。
假定新序列长度是m，其中有k项超过L，这样的序列共有种，递推计算阶乘的乘法逆，再用容斥原理求和即得结果。(代码中打印了进度信息)
n=7500000
tick=1
mod=10**9+9
f=[1,1]
g=[1,1]
h=[1,1]
for i in range(2,n+1):
f.append((f[-1]*i)%mod)
h.append((-h[mod%i]*(mod//i))%mod)
g.append((g[-1]*h[i])%mod)
binom=lambda m,k:(f[m]*g[m-k]*g[k])%mod
print "initialization completed, start computing..."
res=0
for k in range(1,n+1):
res=(res+pow(-(n-1),k-1,mod)*(sum(pow(n,i+1,mod)*binom(k+i,i)-(pow(n,i,mod)*binom(k+i-1,i-1) if i>0 else 0) for i in range(n-k,-1,-k))%mod))%mod
if k%tick==0:
print k,"out of", n,"completed, current result:", res
if tick < 75:
tick+=1
else:
tick*=10
print res%mod
|
