Project Euler 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$.

解决方案

一个结论：一个数字串$s$的置换数的值为$\displaystyle{\sum{i=1}^n\sum{j=i+1}^n [si>s_j]}$，其中$[]$表示示性函数，$n$为字符串$s$的长度。因此这题的主要思路是，统计$\displaystyle{f(s,x,y)=\sum{i=1}^n\sum{j=i+1}^n [s_i=x\land s_j=y]}$的数对数量，并且计算$\displaystyle{\sum{x=1}^9\sum_{j=i+1}^9f(s,x,y)}$的值即可。并且，$f(s,x,y)$的值可以通过前缀和以$O(n)$的时间复杂度计算出来。

此外，令$ci(i\in{1,2,3,\dots,8,9})$表示数字$i$的因子个数。那么按照题意，其整除列的个数为$\displaystyle{M=\prod{i=1}^n c{s_i}}$.并且，令$\displaystyle{g(x,y)=\sum{a\mid x,b\mid y}[a>b]}$。对于一对下标$(i,j)$，其中$i<j$，那么这对下标的贡献为$\dfrac{M\cdot g(si,s_j)}{c{si}\cdot c{s_j}}$。使用上面的方法统计不同的元素对再求和，得到最终答案为：

$$M\cdot\sum_{x=1}^9\sum_{y=1}^9\dfrac{f(s,x,y)\cdot g(x,y)}{c_x\cdot c_y}.$$

代码

#include <bits/stdc++.h>
# include "tools.h"
using namespace std;
typedef long long ll;

const int N=1e8;
ll mod=1e9+7;

const int B=10;
int c[B]={0, 1, 2, 2, 3, 2, 4, 2, 4, 3};
int g[B][B] ={
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {0, 1, 2, 1, 2, 1, 2, 1, 2, 1},
        {0, 2, 3, 3, 3, 2, 4, 2, 3, 3},
        {0, 1, 2, 2, 3, 1, 3, 1, 3, 2},
        {0, 3, 5, 4, 6, 4, 6, 3, 6, 4},
        {0, 1, 2, 2, 3, 2, 4, 1, 3, 2},
        {0, 3, 5, 5, 6, 4, 8, 4, 6, 5},
        {0, 2, 4, 3, 5, 3, 6, 3, 6, 3},
};
vector<int>s;
ll cnt[B][B],inv[B];
int d[B];
int main(){
    for(int i=1;i<B;i++)
        inv[i] = mod_inverse(i,mod);
    vector<int>v=get_prime(N-1);
    for(int p:v){
        int pre=s.size();
        for(int m=p;m;m/=10)
            if(m % 10)
               s.push_back(m%10);
        reverse(s.begin()+pre,s.end());
    }
    for(int x:s){
        for(int j=0;j<B;j++)
            cnt[j][x] += d[j];
        ++d[x];
    }
    ll nums=1;
    for(int i=1;i<B;i++)
        nums=nums*qpow(c[i],d[i],mod)%mod;
    ll ans=0;
    for(int i=1;i<B;i++)
        for(int j=1;j<B;j++)
            ans+=cnt[i][j]%mod*nums%mod*inv[c[i]]%mod*inv[c[j]]%mod*g[i][j];
    ans%=mod;
    printf("%lld\n",ans);
}