Project重排

考虑组成单词project的字母所构成的字符集$A=\{c,e,j,o,p,r,t\}$。

记$T(n)$是由A中的字符所构成的长度为n且不含project的5040种重排中的任何一种作为子串的字符串总数。

可以验证$T(7)=77-7!=818503$，求$T(10^{12})$的最后9位数字。

本题难度:

解答

不难理解，本题就是要求由7个字符组成、长度为n、且任意7个连续字符中至少一对相同字符的字串总数。\\ 设$f^{(n)}_k$是符合要求、长度为n且最后6个字符中已经出现中了k种不同字符的字符串总数，那么可得 $$\begin{pmatrix} f^{(n)}_1\\ f^{(n)}_2\\ f^{(n)}_3\\ f^{(n)}_4\\ f^{(n)}_5\\ f^{(n)}_6\\ \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1\\ 6 & 1 & 1 & 1 & 1 & 1\\ 0 & 5 & 1 & 1 & 1 & 1\\ 0 & 0 & 4 & 1 & 1 & 1\\ 0 & 0 & 0 & 3 & 1 & 1\\ 0 & 0 & 0 & 0 & 2 & 1 \end{pmatrix} \begin{pmatrix} f^{(n-1)}_1\\ f^{(n-1)}_2\\ f^{(n-1)}_3\\ f^{(n-1)}_4\\ f^{(n-1)}_5\\ f^{(n-1)}_6\\ \end{pmatrix}$$ 用矩阵快速幂计算即得结果$423341841$。

n=10**12
m=7
mod=10**9

mul=lambda A,B:[[sum(A[i][k]*B[k][j] for k in range(len(B)))%mod for j in range(len(B[0]))] for i in range(len(A))]

a=[[m]+[0]*(m-2)]
b=[[1 if j<=i else (m-i-1 if j==i+1 else 0) for j in range(m-1)] for i in range(m-1)]        
n-=1
while n:
    if n&1:
        a=mul(a,b)
    b=mul(b,b)
    n>>=1

print sum(a[0])%mod