题解：CF2039F1 Shohag Loves Counting (Easy Version)

· · 题解

我没有莫比乌斯反演😋

从大到小考虑字段长度，容易发现整个序列的最大值一定在最左侧或最右侧，再往下递归就得出了序列是单谷。

现在问题转化成了，对所有递减序列计数，要求所有前缀的 gcd 不同（即递减），长度为 n 的序列的权值是 2^{n-1}，求总权值。

考虑 dp，设 f_{i,j} 表示序列总的 gcd 为 i，最后一个数为 j 的权值和。转移：

f_{i,j}=\sum_S \sum_K [\gcd(Si,j)=i][Si\times K>j]f_{Si,Si\times K}\times 2 + [i=j]

不妨先忽略 gcd 的限制，直接枚举 S,K，贡献是一个前缀的形式，容易差分去做。

考虑算多了什么，也就是说我们从一个 f_{Si,SiK} 在后面拼上 j 后 gcd 是某个 i 的倍数 S'i。由于所有大于 i 的 dp 值都已算出，对于 f_{i,j} 直接减去所有的 f_{S'i,j}，意义就是 f_{S'i,j} 的最后一步拼上 j 后，我错把 gcd 当作了 i 转移到 f_{i,j}，所以要减去。

此时还有一些问题，就是如果原来 gcd 是 Si，拼上 j 后没变，此时这里的贡献不会被减去，因为 f_{Si,j} 拼上 j 之前的 gcd 是大于 Si 的，它的权值里面是不包含这种情况的。

此时我们只需要在开始转移前缀时不转移给 Si 的倍数，体现在代码里就是算完差分后再把 Si 对 Si 倍数的贡献减掉。

最后，由于 f_{Si,Si} 拥有一个特殊的权值，就是它可以单放一个数，前面的 gcd 是滚木，所以会把 f_{i,Si} 多减一，最后的最后加回来就好了。

分析一下复杂度，f_{i,j} 不是 0 至少要 i|j，上面的转移相当于枚举了每个 i 的倍数及 i 倍数的倍数，可以分析到 \mathcal{O}(m^{4/3}\ln m)，轻松通过。

::::success[AC code]

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define f(i,j,n) for(int i=(j);i<=(n);i++)
#define F(i,n,j) for(int i=(n);i>=(j);i--)
#define rep(v,x) for(auto v:x)
#define per(v,x) for(auto it=(x).rbegin();it!=(x).rend();++it)if (auto v=*it;true)
#define updmax(a,b) a=max(a,b)
#define updmin(a,b) a=min(a,b)
#define updsum(a,b) a=(a+(b))%mod
#define updtim(a,b) a=a*(b)%mod
#define pb push_back
#define arr(x) array<int,x>
#define pri_grt(x) x,vector<x>,greater<x>
using namespace std;
typedef pair<int,int> pii;
namespace fsd{
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
    const int MAXSIZE=1<<20;
    char buf[MAXSIZE],*p1,*p2;
    inline int read(){
        int ak=0,ioi=1;char c=gc();
        while(!isdigit(c)){if(c=='-')ioi=-1;c=gc();}
        while(isdigit(c))ak=ak*10+(c^48),c=gc();
        return ak*ioi;
    }
    inline string reads(){
        string o="";
        char p=gc();
        while(p>'z'||p<'a'){p=gc();}
        while(p<='z'&&p>='a'){o+=p;p=gc();}
        return o;
    }
    inline char readc(){
        char p=gc();
        while(!((p<='z'&&p>='a')||(p<='Z'&&p>='A'))){p=gc();}
        return p;
    }
    inline long double readd(){
        long double ak=0;int ioi=1;char c=gc();
        while(!isdigit(c)){if(c=='-')ioi=-1;c=gc();}
        while(isdigit(c))ak*=10,ak+=c-'0',c=gc();
        if(c=='.'){
            c=gc();
            long double q=0.1;
            while(isdigit(c))ak+=(c-'0')*q,q*=0.1,c=gc();
        }
        return ak*ioi;
    }
}
using namespace fsd;
#define NXD
const int N=1e5+10;
const int mod=998244353;
int IOI[N*20],*IOIx=IOI,*dp[N];
int m;
void gs(){
    m=read();
    IOIx=IOI;
    f(i,1,m)dp[i]=IOIx,IOIx+=m/i;
    for(int *i=IOI;i<IOIx;i++)*i=0;
    F(i,m,1){
        for(int x=i*2;x<=m;x+=i)for(int y=x,c=0;y<=m;y+=x,c++)updsum(dp[i][y/i-2],dp[x][c]*2);
        for(int c=m/i-2;c>=0;c--)updsum(dp[i][c],dp[i][c+1]);
        for(int x=i*2;x<=m;x+=i)for(int c=m/x-1,y=(c+1)*x,sm=0;c>=0;y-=x,c--)updsum(sm,dp[x][c]),updsum(dp[i][y/i-1],-sm),updsum(sm,dp[x][c]);
        f(c,0,m/i-1)dp[i][c]++;
    }
    int ans=0;
    f(i,1,m)f(c,0,m/i-1)updsum(ans,dp[i][c]);
    printf("%lld\n",(ans+mod)%mod);
}
#define XXX
signed main(){
#ifndef XXX
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef NXD
    int t=0;cin>>t;while(t--)
#endif
        gs();
    return 0;
}

::::