0427 n序列
* * * *
拉格朗日计划
* * * *
n序列

由恰好n个1到n之间(包括1和n)的自然数组成的序列称为n序列,例如$1, 5, 5, 10, 7, 7, 7, 2, 3, 7$是一个10序列。显然n序列共有$n^n$个。

对于任意序列S,记$L(S)$为其中相同元素连续出现的最大次数,例如若S是上述序列,则$L(S)=3$,因为其中有连续3个7。

记$f(n)$为所有n序列的$L(S)$之和,则可以验证$f(3)=45, f(7)=1403689, f(11)=481496895121$。

求$f(7500000)$模$10^9+9$的余数。

本题难度:



解答

注意本题的模数是$10^9+9$而不是OI比赛中常见的$10^9+7$!

依次记录连续出现的数的次数,如此可得一新序列,例如题面例子中$1, 5, 5, 10, 7, 7, 7, 2, 3, 7$对应的新序列是$1,2,1,3,1,1,1$。

假定新序列长度是m,其中有k项超过L,这样的序列共有$n(n-1)^{m-1}\binom{n-k(L-1)-L}{m-L}\binom{m}{k}$种,递推计算阶乘的乘法逆,再用容斥原理求和即得结果$97138867$。(代码中打印了进度信息)

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