0%

Problem 705


Problem 705


Total Inversion Count of Divided Sequences

The inversion count of a sequence of digits is the smallest number of adjacent pairs that must be swapped to sort the sequence.
For example, $34214$ has inversion count of $5$: $34214 \to 32414 \to 23414 \to 23144 \to 21344 \to12344$.

If each digit of a sequence is replaced by one of its divisors a divided sequence is obtained.
For example, the sequence $332$ has $8$ divided sequences: ${332,331,312,311,132,131,112,111}$.

Define $G(N)$ to be the concatenation of all primes less than $N$, ignoring any zero digit.
For example, $G(20) = 235711131719$.

Define $F(N)$ to be the sum of the inversion count for all possible divided sequences from the master sequence $G(N)$.
You are given $F(20) = 3312$ and $F(50) = 338079744$.

Find $F(10^8)$. Give your answer modulo $1\ 000\ 000\ 007$.


整除列的逆序对数

一个数字序列的逆序对数是指通过交换相邻数字对序列进行排序时所需的步数。
例如,序列$34214$的逆序对数为$5$:$34214 \to 32414 \to 23414 \to 23144 \to 21344 \to12344$。

将数字序列中的每个数字替换为其约数,得到的新序列称为其整除列
例如,序列$332$有$8$个整除列:${332,331,312,311,132,131,112,111}$。

记$G(N)$为连接所有小于$N$的质数所构成的序列(不包含前导零)。例如,$G(20) = 235711131719$。

记$F(N)$为$G(N)$的所有整除列的逆序对数之和。
已知$F(20) = 3312$,$F(50) = 338079744$。

求$F(10^8)$并将你的答案对$1\ 000\ 000\ 007$取余。