Educational Codeforces Round 151 F. Swimmers in the Pool

一.前言

本来打算打打这个比赛玩玩，结果同学找我打游戏王去了，就没打现场(逃)

因为是一道不错的数学题，来写写补题的题解

这里点名批评 @HOLIC_2022 喂给我的假题意，让我查错大半天，最后发现题意错了还重新推了好多东西，拳头都硬了

等会儿顺便分享下假题意的一种做法

二.正文

简单题意:

有n个人，速度为属于[1,200000]的两两不等的正整数。现有一个长度为l的跑道，一开始每个人都在跑道的起点位置，每个人从起点开始，跑到跑道对面再跑回来再跑过去。。。。。。一直持续T个单位的时间，问，不算0时刻，有多少个时刻至少有两个人会相遇(就是在跑道的相同位置)。($1\le T\mathrm{、}l\le 10^{9}1\backslash leq\; T、l\; \backslash leq\; 10^9$)

假题意:

前面的条件一样，设$F(x,y)F(x,y)$表示x和y在过程中相遇次数，求${\sum }_{i=1}^n{\sum }_{j=i+1}^{n}F(i,j)\backslash sum\_\{i=1\}^\{n\}\backslash sum\_\{j=i+1\}^nF(i,j)$

真题意题解：

我们设t时刻，有两个人跑的距离分别为x和y(不妨设x>y，也就是第一个人的速度比第二个人快)，那么，如果他们两个人相遇，一定有:

这两个条件至少一个成立。

首先考虑$x+y\mathrm{m}\mathrm{o}\mathrm{d}2l=0x+y\; \backslash mod\; 2l\; =\; 0$，设两人的速度分别为$v_1\mathrm{、}{v}_{2}v\_1、v\_2$($v_1>v_{2}v\_1>v\_2$)，当前时间为$tt$，那么很明显有:

$(v_1+v_2)t\mathrm{m}\mathrm{o}\mathrm{d}2l=0(v\_1+v\_2)t\; \backslash mod\; 2l\; =\; 0$

很明显$t\in (0,T],t\in Rt\; \backslash in\; (0,T],\; t\; \backslash in\; R$，那么，所有满足条件的次数很明显有:

$[\frac{(v_1+v_2)T}{2l}][\backslash frac\{(v\_1+v\_2)T\}\{2l\}]$(其实就是算一共有多少个2l能到达)。

设这个值为$kk$，那么对应的时间就分别是:

$\frac{2l}{(v_1+v_2)}\mathrm{、}\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{、}\frac{2kl}{(v_1+v_2)}\backslash frac\{2l\}\{(v\_1+v\_2)\}、...、\backslash frac\{2kl\}\{(v\_1+v\_2)\}$

同理，$x-y\mathrm{m}\mathrm{o}\mathrm{d}2l=0x-y\; \backslash mod\; 2l\; =\; 0$时，次数也就是$[\frac{(v_1-v_2)T}{2l}][\backslash frac\{(v\_1-v\_2)T\}\{2l\}]$，对应时间也就是

$\frac{2l}{(v_1-v_2)}\mathrm{、}\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{、}\frac{2kl}{(v_1-v_2)}\backslash frac\{2l\}\{(v\_1-v\_2)\}、...、\backslash frac\{2kl\}\{(v\_1-v\_2)\}$

注意到，两种状态下并无本质不同，我们只需要知道对于一个数$ii$，是否存在两个速度和为$ii$或者差为$ii$，然后就可以获得有存在至少两点相遇的时间了(有多个等于$ii$,因为时间都一样，统计一个就好)

那么，我们如何求解上述问题呢？

我们考虑多项式。

设

那么， 我们使用$FFTFFT$或者$NTTNTT$，求一遍$F\ast FF*F$，$[x^n]F\ast F[x^n]F*F$的意义是，先从n个速度中选出一个速度，再从n个速度中选出一个速度，使得两个速度和为n的方案数，在这基础上，我们减去两次选择的速度都是同一个人的情况，如果当前的系数不为0，那么，就能说明存在两个速度和为$ii$

对于差，我们求一遍$F\ast F^{-1}F*F^\{-1\}$就行了，因为$F^{-1}F^\{-1\}$的$ii$项是是否存在一个人速度为$maxn-imaxn\; -\; i$，那么乘出来后的第$ii$项就是差为$maxn-imaxn-i$的方案数。

我们求完之后，会很明显发现，答案大了。那是因为各个值所对应的时间是有重叠部分的。

接下来就是考虑如何进行去重。

注意到，每个时间的形式都是$\frac{2kl}{i}\backslash frac\{2kl\}\{i\}$的形式，因为我们只需要去重，那么我们不妨把多余的$2l2l$部分去掉，看做$\frac{k}{i}\backslash frac\{k\}\{i\}$这种形式。

我们可以很简单的想到一种去重的方法:将所有分数画出最简，然后再把相同的分数去除即可。

这里我们考虑使用莫比乌斯反演。

我们设$A[i]=\mathrm{化}\mathrm{为}\mathrm{最}\mathrm{简}\mathrm{分}\mathrm{数}\mathrm{后}\mathrm{，}\mathrm{分}\mathrm{母}\mathrm{为}i\mathrm{的}\mathrm{分}\mathrm{数}\mathrm{的}\mathrm{个}\mathrm{数}\mathrm{，}B[i]=\mathrm{化}\mathrm{为}\mathrm{最}\mathrm{简}\mathrm{分}\mathrm{数}\mathrm{后}\mathrm{，}\mathrm{分}\mathrm{母}\mathrm{为}i\mathrm{的}\mathrm{因}\mathrm{子}\mathrm{的}\mathrm{分}\mathrm{数}\mathrm{的}\mathrm{个}\mathrm{数}A[i]=化为最简分数后，分母为i的分数的个数，B[i]=化为最简分数后，分母为i的因子的分数的个数$

那么根据定义有:$Ans={\sum }_{i=1}^{maxn}A[i],B[i]={\sum }_{j\mathrm{\mid }i}A[j]Ans\; =\; \backslash sum\_\{i=1\}^\{maxn\}A[i],B[i]=\backslash sum\_\{j|i\}A[j]$

那么，根据莫比乌斯反演有:

$A[i]={\sum }_{j\mathrm{\mid }i}B[j]\ast u[\frac{i}{j}]A[i]=\backslash sum\_\{j|i\}B[j]*u[\backslash frac\{i\}\{j\}]$

所以，我们只需要求出$B[i]B[i]$就行了。

注意到，一开始未化简的相同分母的分数的分子都是从1开始递增的。所以，对于一种分母$i,B[i]i,B[i]$代表的就是分母为$ii$时，最大的分子是多少

我们先令存在速度和或者差为$ii$的那些$B[i]=\frac{Ti}{2l}B[i]\; =\; \backslash frac\{Ti\}\{2l\}$。

考虑到一个分数化简只可能从当前分母的倍数化简过来，那么，我们对于当前枚举的分母$ii$，我们再枚举它的倍数即可。

对于$ii$的一个倍数$p\ast ip*i$，能以它为分母的分数的分子是$1-B[p\ast i]1-B[p*i]$，那么，它们分母化简成$ii$后，分子就是$1-[\frac{B[p\ast i]}{p}]1-[\backslash frac\{B[p*i]\}\{p\}]$，所有倍数取max即可。

最后，再带入莫比乌斯反演公式，就行了。

唯一需要注意一点的就是，对于不可能成为分母的那些数字，不要统计答案，不然会出错

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 6e5 + 10, mod = 1e9 + 7, Mod = 998244353, mod1 = 3, mod2 = 332748118;
const int M = 2e5;
int rs[N], u[N];
bool f[N];
int F[N], G[N], id[N];
int r[N], K, l;
int p[N], cnt;
inline void sai(){
	u[1] = 1;
	for(int i = 2; i < N; ++ i){
		if(!f[i]){
			p[++ cnt] = i; u[i] = -1;
		}
		for(int j = 1; j <= cnt; ++ j){
			if(i * p[j] >= N) break;
			f[i * p[j]] = 1;
			if(i % p[j] == 0){
				u[i * p[j]] = 0;
				break;
			}
			u[i * p[j]] = -u[i];
		}
	}
}
inline int ksm(int x, int y){
	int ans = 1;
	while(y){
		if(y & 1) ans = (1LL * ans * x) % Mod;
		x = (1LL * x * x) % Mod; y >>= 1;
	}
	return ans;
}
inline void NTT(int *v, int tp){
	for(int i = 1; i < K; ++ i){
		if(r[i] > i) swap(v[r[i]], v[i]);
	}
	for(int i = 1; i < K; i <<= 1){
		int w1 = ksm(tp, (Mod - 1) / (i << 1));
		for(int R = i << 1, j = 0; j < K; j += R){
			int w = 1;
			for(int k = 0; k < i; ++ k){
				int x = v[j + k], y = (1LL * w * v[i + j + k]) % Mod;
				v[j + k] = (x + y) % Mod;
				v[i + j + k] = (x - y + Mod) % Mod;
				w = (1LL * w * w1) % Mod;
			}
		}
	}
}
inline void pre(int al){
	K = 1, l = 0;
	while(K <= al) K <<= 1, ++ l;
	for(int i = 1; i < K; ++ i) r[i] = ((r[i >> 1] >> 1) | (i & 1) << (l - 1));
}
inline void Mul(int *a, int *b){
	NTT(a, mod1); if(a != b) NTT(b, mod1);
	for(int i = 0; i < K; ++ i) a[i] = (1LL * a[i] * b[i]) % Mod;
	NTT(a, mod2); int inv = ksm(K, Mod - 2);
	for(int i = 0; i < K; ++ i) a[i] = (1LL * a[i] * inv) % Mod;
}
signed main(){
	sai();
	int l, t, n;
	scanf("%lld%lld%lld", &l, &t, &n);
	for(int x, i = 1; i <= n; ++ i){
		scanf("%lld", &x);
		id[x] = F[x] = 1;
	}
	pre(M << 1); Mul(F, F);
	int ans = 0;
	for(int i = 3; i < K; ++ i){//和至少是3
		if(i % 2 == 0) F[i] -= (id[i / 2]);
		rs[i] = (F[i] > 0);
	}
	memset(F, 0, sizeof(F));
	for(int i = 0; i <= M; ++ i){
		F[i] = id[i]; G[i] = id[M - i];//G = F'
	}
	pre(M << 1); Mul(F, G);
	for(int i = 0; i < M; ++ i){
		int v = (M - i); //x - y的值
		rs[v] |= (F[i] > 0);
	}
	memset(F, 0, sizeof(F)); memset(G, 0, sizeof(G));
	for(int i = 1; i < N; ++ i){
		if(rs[i]) F[i] = (1LL * t * i) / (2LL * l);
	}
	for(int i = 1; i < N; ++ i){//求可以作为分母的数字
		for(int j = i + i; j < N; j += i){
			rs[i] |= rs[j];
		}
	}
	//设F[i] = 化简后分母为i的因子的分数的个数
	//G[i] = 化简后分母为i的个数
	//F[i] = G[j] (j|i)
	//G[i] = F[j] * u[i / j] (j|i)
	//求F[i]即可 
	for(int i = N - 1; i; -- i){//正着反着都一样，因为要最大肯定是从初始化的那些数字转移过了
		for(int j = i + i; j < N; j += i){
			F[i] = max(F[i], F[j] / (j / i));
		}
	}
	for(int i = 1; i < N; ++ i){
		for(int j = i; j < N; j += i){
			G[j] += F[i] * u[j / i];
		}
	}
	for(int i = 1; i < N; ++ i){
		if(rs[i]) ans = (ans + G[i]) % mod;
	} 
	printf("%d", ans);
	return 0;
} 

假题意题解

一开始思路是一样的，我们可以通过$FFT\mathrm{/}NTTFFT/NTT$求出和/差为$ii$的有多少种方案。然后，对于每种我们都计算下有多少种方案。也就是，我们分别求有多少个$x+y\mathrm{m}\mathrm{o}\mathrm{d}2l=0x+y\; \backslash mod\; 2l\; =\; 0$以及$x-y\mathrm{m}\mathrm{o}\mathrm{d}2l=0x\; -\; y\; \backslash mod\; 2l\; =\; 0$，我们注意到，我们重复计算了两者同时成立的情况，也就是$x\mathrm{m}\mathrm{o}\mathrm{d}2l=y\mathrm{m}\mathrm{o}\mathrm{d}2l=0x\; \backslash mod\; 2l\; =\; y\; \backslash mod\; 2l\; =\; 0$以及$x\mathrm{m}\mathrm{o}\mathrm{d}2l=y\mathrm{m}\mathrm{o}\mathrm{d}2l=lx\; \backslash mod\; 2l\; =\; y\; \backslash mod\; 2l\; =\; l$的情况，我们将答案减去这两种情况的答案即可。

对于第一种情况，我们有:

也就是两人正好都跑完了若干个来回，此时时间相等

化简得:

$k{v}_2=t{v}_{1}kv\_2=tv\_1$

注意到，当$k{v}_2=t{v}_{1}kv\_2=tv\_1$为$lcm(v1,v2)lcm(v1,\; v2)$的倍数，也就是说，我们求最高能到$lcmlcm$的多少倍就行了。

设$k^{\mathrm{\prime }}{v}_2=t^{\mathrm{\prime }}{v}_1=lcm(v_1,v_2)k\text{'}v\_2\; =\; t\text{'}v\_1\; =\; lcm(v\_1,\; v\_2)$

容易得，最高倍数为:

$[\frac{T}{\frac{2k^{\mathrm{\prime }}l}{v_1}}][\backslash frac\{T\}\{\backslash frac\{2k\text{'}l\}\{v\_1\}\}]$

$=[\frac{Tv1}{2k^{\mathrm{\prime }}l}]=[\backslash frac\{Tv1\}\{2k\text{'}l\}]$

又有$k^{\mathrm{\prime }}{v}_2=lcmk\text{'}v\_2\; =\; lcm$可得，$k^{\mathrm{\prime }}=\frac{lcm}{v_2}k\text{'}\; =\; \backslash frac\{lcm\}\{v\_2\}$

代入得:

$[\frac{T{v}_1{v}_2}{2l\ast lcm}][\backslash frac\{Tv\_1v\_2\}\{2l*lcm\}]$

又因为$lcm=\frac{v_1{v}_2}{gcd}lcm\; =\; \backslash frac\{v\_1v\_2\}\{gcd\}$

代入得:

$[\frac{T\ast gcd}{2l}][\backslash frac\{T*gcd\}\{2l\}]$

因为，我们可以直接枚举$gcdgcd$

所以，我们只需要求，对于一个数$ii$，速度两两求$gcdgcd$后，有多少组的$gcdgcd$为$ii$即可。

要求它，我们设$c[i]=\mathrm{有}\mathrm{多}\mathrm{少}\mathrm{个}\mathrm{速}\mathrm{度}\mathrm{是}i\mathrm{的}\mathrm{倍}\mathrm{数}c[i]=有多少个速度是i的倍数$，那么，$gcd\mathrm{为}i\mathrm{的}\mathrm{倍}\mathrm{数}\mathrm{的}\mathrm{个}\mathrm{数}\mathrm{就}\mathrm{是}\frac{c[i]\ast (c[i]-1)}{2}gcd为i的倍数的个数就是\backslash frac\{c[i]*(c[i]\; -\; 1)\}\{2\}$，我们当然可以莫比乌斯反演，当然也可以直接倒着容斥一遍即可。

对于$x-y\mathrm{m}\mathrm{o}\mathrm{d}2l=lx-y\; \backslash mod\; 2l\; =\; l$的部分，我们同样写出表达式:

$\frac{(2k+1)l}{v_1}=\frac{(2t+1)}{v_2}\backslash frac\{(2k+1)l\}\{v\_1\}=\backslash frac\{(2t+1)\}\{v\_2\}$

化简:

$(2k+1)v2=(2t+1)v1(2k+1)v2\; =\; (2t+1)v1$

也就是，两者的速度的奇数倍要相等。

这部分比较特殊，我们要这么做:

将所有速度表示为$2^k\ast x2^k*x$，其中$k\ge 0,xk\; \backslash ge\; 0,\; x$为奇数，我们将所有速度按$kk$分类。

注意到，只有同一组的速度才可能满足条件，所以我们只看同一组的情况。

对于同一组，两者的到达$lcmlcm$的倍数一定是奇数(用$lcmlcm$的表达式可证)

而每个倍数又是$lcmlcm$的倍数，那么，我们可以类比之前的做法，然后我们只需要统计所有奇数倍有多少个即可。

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 6e5 + 10, mod = 1e9 + 7, Mod = 998244353, mod1 = 3, mod2 = 332748118;
const int M = 2e5;
int cnt[N];
int rs[N], c[N], d[N];
int F[N], G[N], id[N];
int r[N], K, l;
inline int ksm(int x, int y){
	int ans = 1;
	while(y){
		if(y & 1) ans = (1LL * ans * x) % Mod;
		x = (1LL * x * x) % Mod; y >>= 1;
	}
	return ans;
}
inline void NTT(int *v, int tp){
	for(int i = 1; i < K; ++ i){
		if(r[i] > i) swap(v[r[i]], v[i]);
	}
	for(int i = 1; i < K; i <<= 1){
		int w1 = ksm(tp, (Mod - 1) / (i << 1));
		for(int R = i << 1, j = 0; j < K; j += R){
			int w = 1;
			for(int k = 0; k < i; ++ k){
				int x = v[j + k], y = (1LL * w * v[i + j + k]) % Mod;
				v[j + k] = (x + y) % Mod;
				v[i + j + k] = (x - y + Mod) % Mod;
				w = (1LL * w * w1) % Mod;
			}
		}
	}
}
inline void pre(int al){
	K = 1, l = 0;
	while(K <= al) K <<= 1, ++ l;
	for(int i = 1; i < K; ++ i) r[i] = ((r[i >> 1] >> 1) | (i & 1) << (l - 1));
}
inline void Mul(int *a, int *b){
	NTT(a, mod1); if(a != b) NTT(b, mod1);
	for(int i = 0; i < K; ++ i) a[i] = (1LL * a[i] * b[i]) % Mod;
	NTT(a, mod2); int inv = ksm(K, Mod - 2);
	for(int i = 0; i < K; ++ i) a[i] = (1LL * a[i] * inv) % Mod;
}
signed main(){
	int l, t, n;
	scanf("%lld%lld%lld", &l, &t, &n);
	for(int x, i = 1; i <= n; ++ i){
		scanf("%lld", &x);
		id[x] = F[x] = 1;
	}
	pre(M << 1); Mul(F, F);
	int ans = 0, inv2 = (mod + 1) >> 1;
	for(int i = 3; i < K; ++ i){
		if(i % 2 == 0) F[i] -= (id[i / 2]);
		F[i] = (1LL * F[i] * inv2) % mod; //因为x + y = y + x，会重复计算一遍，所以要除2 
		cnt[i] = F[i];
	}
	memset(F, 0, sizeof(F));
	for(int i = 0; i <= M; ++ i){
		F[i] = id[i]; G[i] = id[M - i];
	}
	pre(M << 1); Mul(F, G);
	for(int i = 0; i < M; ++ i){
		int v = (M - i); //x - y的值,因为不考虑x = y(此时对应M)，所以x - y 不等于 y - x，不用除2
		cnt[v] = (cnt[v] + F[i]) % mod;
	}
	for(int i = 1; i <= M; ++ i){
		for(int j = i; j <= M; j += i){
			c[i] += id[j];
		}
	}
	for(int i = M; i; -- i){
		d[i] = (1LL * c[i] * (c[i] - 1)) % mod;
		d[i] = (1LL * d[i] * inv2) % mod;
		for(int j = i + i; j <= M; j += i){
			d[i] = (d[i] - d[j] + mod) % mod;
		}
		cnt[i] = (cnt[i] - d[i] + mod) % mod;
	}
	memset(c, 0, sizeof(c));
	for(int T = 0; T <= 17; ++ T){//分组
		int x = (1 << T), y = (1 << (T + 1));
		for(int i = 1; i <= M; ++ i){
			for(int j = i; j <= M; j += i){
				if(j % x == 0 && j % y != 0) c[i] += id[j];
			}
		}
		for(int i = M; i; -- i){
			d[i] = (1LL * c[i] * (c[i] - 1)) % mod;
			d[i] = (1LL * d[i] * inv2) % mod;
			for(int j = i + i; j <= M; j += i){
				d[i] = (d[i] - d[j] + mod) % mod;
			}
			int now = ((1LL * t * i) / (2LL * l));
			now = (now + 1) / 2;//统计奇数倍个数
            now %= mod;
			now = (1LL * now * d[i]) % mod;
			ans = (ans - now + mod) % mod;
		}
		for(int i = 1; i <= M; ++ i) c[i] = 0;
	}
	for(int i = 1; i < N; ++ i){
		int now = ((1LL * t * i) / (2LL * l)) % mod;
		now = (1LL * now * cnt[i]) % mod;
		ans = (ans + now) % mod;
	}
	printf("%d", ans);
	return 0;
}