题解：P11418 [Sloi 2024]D1T2 简单的反链求和问题

· · 题解

新年第一题。

首先考虑如何算 f(n)。设 n=\prod_i p_i^{k_i}，可以发现 f(n) 只与 k_i 有关。但是还是难以计算 f(n)，此时我们需要一个结论：

令 \Omega(n) 为 n 的质因数分解中的 k_i 之和。则一定存在一种最优解使得任意两个被选中的数 a,b 都满足 \Omega(a)=\Omega(b)。

这个结论我还不会证，可能以后会补充完整。

猜出这种构造并不难，因为看起来这种构造就是很优的，且显然有合法性和极大性。

这样我们只需要做背包就能计算 f(n) 了。但是要求的是 f 的前缀和，把 0 去掉后直觉上本质不同的 \{k_i\} 应该是很少的，搜出来一共只有大约 2.3\times 10^4 种，容易对于每种 \{k_i\} 求出其对应的 f(n)。

现在我们只需要算出有多少个 n 质因子次数是 \{k_i\} 即可。直接爆搜除了最后一位以外的位置填哪些质数，最后一位次数如果是 1 则可以使用 Min_25 筛做质数前缀统计，否则能填的最大质数不到 \sqrt n 可以线性筛时直接预处理。可以发现这个东西跑的飞快然后就过了。

#include <algorithm>
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
#include <array>
#include <cmath>

#define rgall(arr) (arr).begin(),(arr).end()
#define rgcnt(arr,cnt) (arr).begin(),(arr).begin()+(cnt)
#define rgo1(arr,cnt) (arr).begin()+1,(arr).begin()+1+(cnt)
#define rgany(arr,cnt,offset) (arr).begin()+(offset),(arr).begin()+(offset)+(cnt)

using namespace std;

array<long long,800000> dpp0,bpos;
const array<int,15>     DFSps={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
array<int,400000>       primes,sump0;
bitset<400000>          isprime;
vector<int>             cntps,sumps;
long long               answer,cntp,n,n2;
int                     divline;

long long fast_pow(long long base,long long exp)
{
    long long result;
    for(result=1;exp;exp&1?result=result*base:true,base=base*base,exp>>=1);
    return result;
}
inline long long xrooti(long long a,int b)
{
    return pow(a,1./b)+1e-10;
}
inline int loc_idx(long long a)
{
    return a>n2?n/a:n2-a+divline;
}
long long DFS_count(int dep,long long a,int pidx)
{
    if(cntps.empty())
        return 1;
    if(dep==cntps.size()-1)
    {
        if(cntps.back()==1)
            return max(0ll,dpp0[loc_idx(a)]-pidx);
        return max(sump0[xrooti(a,cntps.back())]-pidx,0);
    }
    long long result=0;
    for(int i=pidx+1;i<=cntp&&fast_pow(primes[i],sumps[dep])<a;i++)
        result+=DFS_count(dep+1,a/fast_pow(primes[i],cntps[dep]),i);
    return result;
}
void DFS_factor(int dep,long long a,const long long n)
{
    array<int,60> dp{1};
    for(int i:cntps)
        for(int j=59;j;j--)
            for(int k=1;k<=i&&k<=j;k++)
                dp[j]+=dp[j-k];
    int maxc=0;
    for(int i:dp)
        maxc=max(maxc,i);
    sumps=cntps;
    for(int i=(int)cntps.size()-2;i>=0;i--)
        sumps[i]+=sumps[i+1];
    answer+=maxc*DFS_count(0,n,0);
    cntps.push_back(1);
    a=a*DFSps[dep];
    while(a<=n)
    {
        DFS_factor(dep+1,a,n);
        a=a*DFSps[dep],++cntps.back();
    }
    cntps.pop_back();
}

int main(int argc,char* argv[],char* envp[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n,n2=sqrt(n)+1e-9;
    for(int i=2;i<=n2;i++)
    {
        sump0[i]=sump0[i-1];
        if(!isprime[i])
            primes[++cntp]=i,++sump0[i];
        for(int j=1;j<=cntp&&i*primes[j]<=n2;j++)
        {
            isprime.set(i*primes[j]);
            if(!(i%primes[j]))
                break;
        }
    }
    int cntb=0;
    for(long long i=1,j;i<=n;i=n/j+1)
    {
        ++cntb,dpp0[cntb]=(j=bpos[cntb]=n/i)-1;
        if(!divline&&j<=n2)
            divline=cntb;
    }
    for(int i=1;i<=cntp;i++)
        for(int j=1;1ll*primes[i]*primes[i]<=bpos[j];j++)
            dpp0[j]-=dpp0[loc_idx(bpos[j]/primes[i])]-i+1;
    DFS_factor(0,1,n);
    cout<<answer;
    return 0;
}