专栏文章

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

PPurslaneM2GA
P8322题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miq805cz
此快照首次捕获于
2025/12/04 00:27
3 个月前
此快照最后确认于
2025/12/04 00:27
3 个月前
查看原文

Solution

大家好啊，我是安徽队长 Reunite。今天我发明了快速 gcd⁡\gcd 变换，大家快来学习！！！
Reunite 说这是联考的某道题的弱化版（其实一模一样）。他在打模拟赛的时候想到了一个快速 gcd⁡\gcd 变换，我按照他的思路实现了出来。
首先，不妨设 k=1k=1。转化为——任意相邻两个数不互质，任意相邻三个数互质。
设 dpi,j,kdp_{i,j,k} 表示，只考虑前 ii 个数，有多少种数列满足 ai=ja_i = j 且 gcd⁡(ai,ai−1)=k\gcd(a_i,a_{i-1}) = k。显然这样的 (j,k)(j,k) 只有 O(Vln⁡V)O(V \ln V) 对。
考虑转移。枚举 ai+1a_{i+1} 的取值 aa，则有：
dpi+1,a,gcd⁡(a,j)←dpi+1,a,gcd⁡(a,j)+[gcd⁡(a,k)=1]dpi,j,kdp_{i+1,a,\gcd(a,j)} \leftarrow dp_{i+1,a,\gcd(a,j)} + [\gcd(a,k) = 1] dp_{i,j,k}
显然要考虑莫比乌斯反演，枚举 d∣gcd⁡(a,k)d \mid \gcd(a,k) 有：
dpi+1,a0d,gcd⁡(a0d,j)←dpi+1,a0d,gcd⁡(a0d,j)+μ(d)dpi,j,k0ddp_{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}
枚举 dd 的时候，发现第三维已经不重要，所以记录 fj=μ(d)∑k0dpi,j,k0df_j = \mu(d) \sum_{k_0} dp_{i,j,k_0d}。显然 d∣jd \mid j。
我们枚举 a0d=aa_0d = a，相当于做了这样一个事情：
dpi+1,a,gcd⁡(a,j)←dpi+1,a,gcd⁡(a,j)+fjdp_{i+1,a,\gcd(a,j)} \leftarrow dp_{i+1,a,\gcd(a,j)} + f_j
注意到 aa 和 jj 一定都是 dd 的倍数，所以我们可以现将他们除以 dd，做这个运算再乘回去。
考虑一个叫做 gcd⁡\gcd 卷积的东西。给定数组 uiu_i 和 viv_i，我们需要求出 wk=∑gcd⁡(i,j)=kuivjw_k = \sum_{\gcd(i,j) = k} u_iv_j。发现这个东西和 FMT\rm FMT 没啥本质区别，只需要先求狄利克雷后缀和，乘起来再差分即可。
将该操作看为 fjf_j 和 gj=[j=a]g_j=[j=a] 的 gcd\rm gcd 卷积。
如果直接做，比暴力还劣。但是考虑 gjg_j 求狄利克雷后缀和之后只有 O(d(j))O(d(j)) 个非 00 位置，我们只需要处理这些非 00 位置即可。
时间复杂度大概是 O(nVlog⁡2V)O(n V \log^2 V)，卡常能过。
卡常小技巧：避免 vector 循环，避免数组嵌套。
CPP
#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 教我的。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...