Educational Codeforces Round 151 F. Swimmers in the Pool -526互联

一.前言

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

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

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

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

二.正文

简单题意:

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

假题意:

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

真题解：

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

\(\left\{ \begin{aligned} x + y \mod 2l = 0 &&\\ x - y \mod 2l = 0 && \end{aligned} \right. \)

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

首先考虑\(x+y \mod 2l = 0\)，设两人的速度分别为\(v_1、v_2\)(\(v_1>v_2\))，当前时间为\(t\)，那么很明显有:

\((v_1+v_2)t \mod 2l = 0\)

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

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

设这个值为\(k\)，那么对应的时间就分别是:

\(\frac{2l}{(v_1+v_2)}、...、\frac{2kl}{(v_1+v_2)}\)

同理，\(x-y \mod 2l = 0\)时，次数也就是\([\frac{(v_1-v_2)T}{2l}]\)，对应时间也就是

\(\frac{2l}{(v_1-v_2)}、...、\frac{2kl}{(v_1-v_2)}\)

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

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

我们考虑多项式。

设\(F[i]=\left\{ \begin{aligned} 1&&存在一个人的速度为i \\ 0&&不存在一个人的速度为i \end{aligned} \right.\)

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

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

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

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

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

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

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

我们设\(A[i]=化为最简分数后，分母为i的分数的个数，B[i]=化为最简分数后，分母为i的因子的分数的个数\)

那么根据定义有:\(Ans = \sum_{i=1}^{maxn}A[i],B[i]=\sum_{j|i}A[j]\)

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

\(A[i]=\sum_{j|i}B[j]*u[\frac{i}{j}]\)

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

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

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

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

对于\(i\)的一个倍数\(p*i\)，能以它为分母的分数的分子是\(1-B[p*i]\)，那么，它们分母化简成\(i\)后，分子就是\(1-[\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/NTT\)求出和/差为\(i\)的有多少种方案。然后，对于每种我们都计算下有多少种方案。也就是，我们分别求有多少个\(x+y \mod 2l = 0\)以及\(x - y \mod 2l = 0\)，我们注意到，我们重复计算了两者同时成立的情况，也就是\(x \mod 2l = y \mod 2l = 0\)以及\(x \mod 2l = y \mod 2l = l\)的情况，我们将答案减去这两种情况的答案即可。

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

\(\frac{2kl}{v_1} = \frac{2tl}{v_2}(k,t\in N^*、2kl<=Tv_1、2tl <= Tv_2)\)

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

化简得:

\(kv_2=tv_1\)

注意到，当\(kv_2=tv_1\)为\(lcm(v1, v2)\)的倍数，也就是说，我们求最高能到\(lcm\)的多少倍就行了。

设\(k'v_2 = t'v_1 = lcm(v_1, v_2)\)

容易得，最高倍数为:

\([\frac{T}{\frac{2k'l}{v_1}}]\)

\(=[\frac{Tv1}{2k'l}]\)

又有\(k'v_2 = lcm\)可得，\(k' = \frac{lcm}{v_2}\)

代入得:

\([\frac{Tv_1v_2}{2l*lcm}]\)

又因为\(lcm = \frac{v_1v_2}{gcd}\)

代入得:

\([\frac{T*gcd}{2l}]\)

因为\(gcd <= 200000\)，我们可以直接枚举\(gcd\)

所以，我们只需要求，对于一个数\(i\)，速度两两求\(gcd\)后，有多少组的\(gcd\)为\(i\)即可。

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

对于\(x-y \mod 2l = l\)的部分，我们同样写出表达式:

\(\frac{(2k+1)l}{v_1}=\frac{(2t+1)}{v_2}\)

化简:

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

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

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

将所有速度表示为\(2^k*x\)，其中\(k \ge 0, x\)为奇数，我们将所有速度按\(k\)分类。

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

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

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

代码:

#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;
}

educational codeforces swimmers round

educational codeforces round rated

educational codeforces round 151

construction educational codeforces round

cf-educational educational codeforces round

educational codeforces round 147

educational codeforces round 158

educational codeforces contest round

educational codeforces monsters round

educational codeforces balance round