题解：P8322 『JROI-4』少女幻葬

· · 题解

Solution

大家好啊，我是安徽队长 Reunite。今天我发明了快速 \gcd 变换，大家快来学习！！！

Reunite 说这是联考的某道题的弱化版（其实一模一样）。他在打模拟赛的时候想到了一个快速 \gcd 变换，我按照他的思路实现了出来。

首先，不妨设 k=1。转化为——任意相邻两个数不互质，任意相邻三个数互质。

设 dp_{i,j,k} 表示，只考虑前 i 个数，有多少种数列满足 a_i = j 且 \gcd(a_i,a_{i-1}) = k。显然这样的 (j,k) 只有 O(V \ln V) 对。

考虑转移。枚举 a_{i+1} 的取值 a，则有：

dp_{i+1,a,\gcd(a,j)} \leftarrow dp_{i+1,a,\gcd(a,j)} + [\gcd(a,k) = 1] dp_{i,j,k}

显然要考虑莫比乌斯反演，枚举 d \mid \gcd(a,k) 有：

dp_{i+1,a_0d,\gcd(a_0d,j)} \leftarrow dp_{i+1,a_0d,\gcd(a_0d,j)} + \mu(d) dp_{i,j,k_0d}

枚举 d 的时候，发现第三维已经不重要，所以记录 f_j = \mu(d) \sum_{k_0} dp_{i,j,k_0d}。显然 d \mid j。

我们枚举 a_0d = a，相当于做了这样一个事情：

dp_{i+1,a,\gcd(a,j)} \leftarrow dp_{i+1,a,\gcd(a,j)} + f_j

注意到 a 和 j 一定都是 d 的倍数，所以我们可以现将他们除以 d，做这个运算再乘回去。

考虑一个叫做 \gcd 卷积的东西。给定数组 u_i 和 v_i，我们需要求出 w_k = \sum_{\gcd(i,j) = k} u_iv_j。发现这个东西和 \rm FMT 没啥本质区别，只需要先求狄利克雷后缀和，乘起来再差分即可。

将该操作看为 f_j 和 g_j=[j=a] 的 \rm gcd 卷积。

如果直接做，比暴力还劣。但是考虑 g_j 求狄利克雷后缀和之后只有 O(d(j)) 个非 0 位置，我们只需要处理这些非 0 位置即可。

时间复杂度大概是 O(n V \log^2 V)，卡常能过。

卡常小技巧：避免 vector 循环，避免数组嵌套。

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2000+5,MAXM=5000+5,MAXK=43376+5,MOD=998244353;
int n,k,s[MAXM],l[MAXN],r[MAXN],mu[MAXM],flg[MAXM],id[MAXM*MAXM];
ll dp[2][MAXM*MAXM],f[MAXM],tmp[MAXM];
vector<int> pr;
int zzz[MAXM],frac[MAXK],St[MAXM],Lst[MAXM],len[MAXM],pfr[MAXM*20],pc[MAXM];
void init(int mx) {
    mu[1]=1;
    ffor(j,1,mx) for(int i=j;i<=mx;i+=j) zzz[i]++;
    ffor(i,1,mx) St[i]=Lst[i-1]+1,Lst[i]=St[i]+zzz[i]-1;
    ffor(j,1,mx) for(int i=j;i<=mx;i+=j) frac[St[i]+(++len[i])-1]=j;
    ffor(i,2,mx) {
        if(!flg[i]) pr.push_back(i),mu[i]=-1;
        for(auto v:pr) {
            if(i*v>mx) break ;
            flg[i*v]=1;
            if(i%v==0) break ;
            mu[i*v]-=mu[i];
        }
    }
    ffor(i,1,mx) for(auto p:pr) if(i%p==0) pfr[i*11+(++pc[i])]=p;
    return ;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    ffor(i,1,n) cin>>l[i]>>r[i],r[i]=r[i]/k,l[i]=(l[i]+k-1)/k;
//  n=2000,k=1;
//  ffor(i,1,n) l[i]=1,r[i]=5000;
    ffor(i,1,n) if(l[i]>r[i]) return cout<<0,0;
    int tot=0;
    ffor(i,1,5000) s[i]=s[i-1]+5000/i;
    ffor(i,l[1],r[1]) dp[1][i]++;
    init(5000);
    ffor(i,2,n) {
        int st=(i&1),lst=st^1;
        ffor(d,1,5000) if(mu[d]) {
            int m=5000/d;
            ffor(j,1,m) f[j]=0;
            ffor(k,1,m) {int o=k*d;for(int j=k,jj=s[o-1]+1;j<=m;j+=k,jj++) f[j]+=dp[lst][jj];}
            if(mu[d]<0) ffor(j,1,m) f[j]=-f[j];
            for(auto p:pr) {
                if(p>m) break ;
                int ov=m/p*p;
                roff(j,m/p,1) f[j]+=f[ov],ov-=p;    
            }
            ffor(a,1,m) {
                for(int j=St[a],id=frac[j];j<=Lst[a];j++,id=frac[j]) tmp[id]=f[id];
                int k=a*11;
                for(int j=1,p=pfr[k+1];j<=pc[a];j++,p=pfr[k+j]) {int v=a/p;for(int j=St[v],id=frac[j];j<=Lst[v];j++,id=frac[j]) tmp[id]-=tmp[id*p];}
                for(int j=St[a],jj=Lst[a],idx=frac[j];j<=Lst[a];j++,idx=frac[j],jj--) dp[st][s[idx*d-1]+frac[jj]]+=tmp[idx];
            }
        }
        ffor(k,1,5000) for(int j=k,jj=s[k-1]+1;j<=5000;j+=k,jj++) {
            if(k==1||j<l[i]||j>r[i]) dp[st][jj]=0;
            else dp[st][jj]%=MOD;
            dp[lst][jj]=0;
        }
    }
    int ans=0;
    ffor(k,1,43376) ans=(ans+dp[n&1][k])%MOD;
    cout<<(ans%MOD+MOD)%MOD;
    return 0;
}

对了，卡常也是 Reunite 教我的。