超整数

若组成整数n的数字串是组成整数s的数字串的子串，就称s是n的超整数。

例如2718281828是18828的超整数，而314159则不是151的超整数。

令$p(n)$为第n个质数，$c(n)$为第n个合数，则$p(1)=2, p(10)=29, c(1)=4, c(10)=18$。 \begin{align*} \{p(i)\}_{i\in\mathbb N}&=\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \ldots\}, \\ \{c(i)\}_{i\in\mathbb N}&=\{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, \ldots\}. \end{align*} 令$P^D$和$C^D$分别为$\{p(i)\}_{i\in\mathbb N}, \{c(i)\}_{i\in\mathbb N}$中各项的数字根所组成的序列，求一个数的数字根就是把它的各位数都相加，若所得的数超过9，则重复这一过程直至得到一位数为止。 $$P^D=\{2, 3, 5, 7, 2, 4, 8, 1, 5, 2, \ldots\}, \quad C^D=\{4, 6, 8, 9, 1, 3, 5, 6, 7, 9, \ldots\}.$$ 分别令$P_n, C_n$为将$P^D$和$C^D$的前n项连接起来所得的整数，例如$P_{10}=2357248152, C_{10}=4689135679$。

再令$f(n)$为$P_n$和$C_n$的最小公共超整数，例如$f(10)=2357246891352679$，而$f(100) \bmod 1000000007=771661825$。

求$f(10000) \bmod 10^9+7$。

本题难度:

解答

本题要求的是最短公共超串，这可以看成是经典问题最长公共子串问题的变体。

若分别令$c_m, p_n$为第$m$个合数和第$n$个素数，$A(m,n)$为$c_m$和$p_n$的最小公共超整数所形成的字符串，则有 $$A(m,n)=\begin{cases} p_n+A(m-1,n-1) & C_m=P_n, \\ p_n+A(m,n-1) & |A(m,n-1)|<|A(m-1,n)|,\\ p_n+A(m,n-1) & |A(m,n-1)|=|A(m-1,n)|, C_m>P_n, \\ c_m+A(m-1,n) & 其他, \end{cases}$$ 其中$+$表示字符串拼接, $|\cdot|$表示字符串长度，递推计算即得结果$775181359$。

target=105000
d=[0]*target
n=2
while n < target:
    for i in range(n*n,target,n):
        d[i]+=1
    n+=1
    while n < target and d[n]>0:
        n+=1

n=10000
P=[]
C=[]
k=2
while len(P) < n or len(C) < n:
    x=(k-1)%9+1
    if d[k]==0 and len(P) < n:
        P.append(x)
    if d[k]>0 and len(C) < n:
        C.append(x)
    k+=1

L=[[0]*(n+1) for i in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
        if P[i]==C[j]:
            L[i][j]=L[i+1][j+1]+1
        else:
            L[i][j]=max(L[i][j+1],L[i+1][j])

F=[]
i=j=0
while i < n and j < n:
    if P[i]==C[j]:
        F.append(P[i])
        i+=1
        j+=1
    elif P[i] < C[j]:
        if L[i][j]==L[i+1][j]:
            F.append(P[i])
            i+=1
        else:
            F.append(C[j])
            j+=1
    else:
        if L[i][j]==L[i][j+1]:
            F.append(C[j])
            j+=1
        else:
            F.append(P[i])
            i+=1
else:
    F.extend(P[i:])
    F.extend(C[j:])

print int("".join(map(str,F)))%(10**9+7)