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 [s_i>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)\)的时间复杂度计算出来。

此外，令\(c_i(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(s_i,s_j)}{c_{s_i}\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);
}