CF1549

Codeforces Round #736 (Div. 2)

D. Integers Have Friends

题意

给定一个正整数数列 $\{a_n\}$，它的连续子数列为 $a_l\ldots a_r$

求一个最长的连续子数列，$\exists m\geqslant 2$，使 $a_l\equiv a_{l+1}\equiv \ldots \equiv a_{r} \pmod{m}$，也就是它们在模 $m$ 的意义下同余

$n \leqslant 2\cdot 10^5, a_i \leqslant 10^{18}$

思路

可以从同余的定义上思考，$a\equiv b\pmod{m} \iff m|(a-b)$

于是我们就可以写出上面同余式的等价式：$m|(a_l-a_{l+1}),\ldots,m|(a_r-a_{r-1})\quad m\geqslant 2$

进一步有：$m | gcd(a_l-a_{l+1}, \ldots, a_r-a_{r-1})\quad m\geqslant 2$

我们可以将 $m$ 直接取成它们的最大公约数

则当 $gcd(a_l-a_{l+1}, \ldots, a_r-a_{r-1}) \geqslant 2$ 时，一定存在 $m$ 满足题意

令 $b_n=|a_n-a_{n_1}|$，下面讨论针对数列 $\{b_n\}$ 进行

那么问题转换为查找一个最长区间，使得这个区间的数的最大公约数大于等于 $2$

我们可以想想如何快速求解一个区间的最小公约数，类比求区间最小值

我们发现一个区间的最小公约数也是具有可拆分性的，
也就是说 $gcd(a_1,a_2,a_3,a_4)=gcd(gcd(a_1,a_2),gcd(a_3,a_4))$，
于是可以利用线段树，ST表在 $O(logN)$ 下求解任意区间的 $gcd$

那么我们就可以直接枚举左端点 $i$，然后二分最大区间长度 $len$，使 $[i,i+len-1]$ 中的数 $gcd\geqslant 2$
答案就是全局最大的区间长度

如果是线段树实现chk函数：时间复杂度 $O(Nlog^2N)$，二分复杂度一个 $log$，chk函数又一个 $log$

如果是ST表实现chk函数：时间复杂度 $O(NlogN+Nlog10^{18})$，第一项是二分的复杂度，后一项是预处理ST表的复杂度

下面代码我是用ST表实现的

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 2e5 + 10;
int n;
int f[N][20], Log[N];
int a[N];
int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}
void pre() {
	Log[0] = -1;
	for (int i = 1; i < N; i++) {
		Log[i] = Log[i/2] + 1;
	}
}
bool chk(int l, int r) {
	int t = Log[r - l + 1];
	return gcd(f[l][t], f[r - (1 << t) + 1][t]) > 1;
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	pre();
	int T;
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		for (int i = 1; i < n; i++) {
			f[i][0] = a[i+1] - a[i];
			f[i][0] = abs(f[i][0]);
		}
		for (int j = 1; j < 20; j++) {
			for (int i = 1; i + (1 << j) - 1 < n; i++) {
				f[i][j] = gcd(f[i][j-1], f[i+(1<<(j-1))][j-1]);
			}
		}
		int ans = 1;
		for (int i = 1; i < n; i++) {
			int l = 1, r = n - i;
			while (l <= r) {
				int mid = (l+r) >> 1;
				if (chk(i, i + mid - 1)) l = mid+1;
				else r = mid-1;
			}
			ans = max(ans, r+1);
		}
		cout << ans << '\n';
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j < 20; j++) {
				f[i][j] = 0;
			}
			a[i] = 0;
		}
	}
	return 0;
}

E. The Three Little Pigs

题意

给定 $n (1\leqslant n \leqslant 10^6)$ ，有 $Q (1 \leqslant Q \leqslant 2\cdot 10^5)$ 次询问

每次询问给出一个 $x (1\leqslant x \leqslant 3n)$，对于每个 $x$ 求解$\sum_{i=0}^{n} \binom{3i}{x}$的值

注：默认当 $n < m$ 时，$\binom{n}{m} = 0$

思路

法一

由于 $\sum_{i=0}^{n} \binom{3i}{x}$ 中 $3i$ 是间断的，所以我们考虑先把它补全，以充满 $[0,3n)$ 整个区间，这里补全的技巧很高，通过模 $3$ 的最小剩余系中的元素将它补全

令 $f(x, m)=\sum_{i=0}^{n-1} \binom{3i+m}{x}\quad 0\leqslant m\leqslant 2$

那么对于询问 $x$，$ans(x) = f(x,0) + \binom{3n}{x}$

则有第一个方程：

$$f(x,0)+f(x,1)+f(x,2)=\sum_{i=0}^{3n-1}\binom{i}{x}=\binom{3n}{x+1}$$

这里使用了曲棍球恒等式(Hockey Stick Identity)，由于这个数字选择在杨辉三角中的形状像一个曲棍球，也应此得名

$$\text{Hockey Stick Identity:}\quad n\geqslant r, \sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}\\$$

然后我们又可以通过二项式递推式 $\binom{n}{m} = \binom{n-1}{m}+\binom{n-1}{m-1}$ 得到另外两个方程：

$$f(x,1)=f(x,0)+f(x-1, 0)\\ f(x,2)=f(x,1)+f(x-1, 1)$$

通过这三个方程组的联立，解得

$$\begin{cases} f(x,0)=\frac{1}{3}\cdot (\binom{3n}{x+1}-2f(x-1,0)-f(x-1,1))\\ f(x,1)=f(x,0)+f(x-1,0)\\ f(x,2)=f(x,1)+f(x-1,1) \end{cases}$$

于是就可以愉快的递推了

注意：一定要 $O(n)$ 预处理组合数，$3^{-1}$ 也要预处理，不然 $\left\lfloor log_210^9\right\rfloor=29$ 这个常数可不小

$O(n)$ 预处理方法可以见代码
大致思路是先求 $1!\ldots n!$，再求 $(n!)^{-1}$，最后通过 $((n-1)!)^{-1}=(n!)^{-1}\cdot n$ 线性求出每个阶乘的逆元

总复杂度 $O(6N+Q)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 1e9 + 7;
const int N = 3e6 + 10;
int n, Q;
int jie[N], invjie[N];
int ksm(int a, int b) {
	int ret = 1;
	while (b) {
		if (b & 1) ret = (ret * a) % P;
		a = (a * a) % P;
		b >>= 1;
	}
	return ret;
}
int inv(int x) {
	return ksm(x, P-2);
}
int inv3;
void pre() {
	inv3 = inv(3);
	jie[0] = 1;
	for (int i = 1; i < N; i++) {
		jie[i] = (jie[i-1] * i) % P;
	}
	invjie[N-1] = inv(jie[N-1]);
	for (int i = N-2; i >= 0; i--) {
		invjie[i] = (invjie[i+1] * (i+1)) % P;
	}
}
int C(int n, int m) {
	if (n < m) return 0;
	return jie[n] * invjie[m] % P * invjie[n-m] % P;
}
int f[N][2];
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(f, -1, sizeof(f));
	pre();
	cin >> n >> Q;
	for (int i = 0; i <= 3*n; i++) {
		if (i == 0) {
			f[i][0] = f[i][1] = n;
		} else {
			f[i][0] = (((C(3*n, i+1) - 2*f[i-1][0] - f[i-1][1]) % P) + P) % P * inv3 % P;
			f[i][1] = (f[i][0] + f[i-1][0]) % P;
		}
	}
	while (Q--) {
		int x;
		cin >> x;
		cout << (f[x][0] + C(3*n, x)) % P << '\n';
	}
	return 0;
}

法二

利用多项式系数，直接构造答案

令多项式 $P(k) = (1+k)^3 + (1+k)^6 + \ldots + (1+k)^{3n}$

那么对于询问 $x$，$ans(x)$ 就是 $k^x$ 的系数

问题转换为解救 $P(k)$ 多项式，如果用FFT还是会超时，再观察可以看出来它是一个等比数列求和

利用等比数列求和公式，先消去常数项，然后上下项同时除以 $k$，得

$$\begin{aligned} P(k) &= \frac{(1+k)^{3n+3} - (1+k)^3}{(1+k)^3-1}\\ &= \frac{k^{3n+3}+\ldots+(3n+3)k-k^3-3k^2-3k}{k^3+3k^2+3k} \\ &= \frac{k^{3n+2}+\ldots+(3n+3)-k^2-3k-3}{k^2+3k+3} \end{aligned}$$

那么问题转换为：多项式长除法，直接模拟这个过程即可，同样需要预处理组合数，降低复杂度

时间复杂度 $O(3N+Q)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 1e9 + 7;
const int N = 3e6 + 10;
int n, Q;
int jie[N], invjie[N];
int ksm(int a, int b) {
	int ret = 1;
	while (b) {
		if (b & 1) ret = (ret * a) % P;
		a = (a * a) % P;
		b >>= 1;
	}
	return ret;
}
int inv(int x) {
	return ksm(x, P-2);
}
int inv3;
void pre() {
	inv3 = inv(3);
	jie[0] = 1;
	for (int i = 1; i < N; i++) {
		jie[i] = (jie[i-1] * i) % P;
	}
	invjie[N-1] = inv(jie[N-1]);
	for (int i = N-2; i >= 0; i--) {
		invjie[i] = (invjie[i+1] * (i+1)) % P;
	}
}
int C(int n, int m) {
	if (n < m) return 0;
	return jie[n] * invjie[m] % P * invjie[n-m] % P;
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	pre();
	cin >> n >> Q;
	vi num(3*n+3);
	//消去常数项，上下同除k
	for (int i = 0; i < 3*n+3; i++) {
		num[i] = C(3*n+3, i+1);
		if (i <= 2) {
			num[i] = (num[i] - C(3, i+1) + P) % P;
		}
	}
	vi ans(3*n+1);
	//ans[i]就是P(k)中k^i的系数，下面做长除法
	for (int i = 3*n; i >= 0; i--) {
		ans[i] = num[i+2];
		num[i+1] = (num[i+1] - 3*ans[i] + 3*P) % P;
		num[i] = (num[i] - 3*ans[i] + 3*P) % P;
	}
	while (Q--) {
		int x;
		cin >> x;
		cout << ans[x] << '\n';
	}
	return 0;
}

F1. Gregor and the Odd Cows (Easy)

题意

给出 $n$ 个栅栏柱，每个栅栏柱的坐标都是整数并且保证是偶数，三个栅栏柱可以围成一个封闭三角形，被封闭三角形所包围的节点数为奇数个，并且要求三角形的面积为整数，求一共有多少种这样的三角形。

前置芝士

Pick定理

在网格图上的简单多边形的面积 $S$ 有如下公式

$$S = a+\frac{b}{2}-1$$

其中，$a$ 为网格中在多边形内部的节点数，$b$ 为多边形边上的格点数

证明：维基百科 Pick’s theorem

Shoelace公式 (鞋带公式)

令简单多边形的顶点坐标分别为 $(x_i,y_i)\quad i=1\ldots n$

则，该简单多边形的面积为：

$$S=\frac{1}{2}\begin{vmatrix}\sum\limits_{i=1}^{n}det\begin{pmatrix}x_i&y_i\\x_{i+1}&y_{i+1}\end{pmatrix}\end{vmatrix}=\frac{1}{2}\begin{vmatrix}\sum\limits_{i=1}^nx_iy_{i+1}-x_{i+1}y_i\end{vmatrix}\\ x_{n+1}=x_1,y_{n+1}=y_1$$

这个我是用外积理解的(内部的行列式)，具体证明：维基百科 Shoelace formula

它就像的计算关系就像“系鞋带”一样

思路

如果没有Pick定理真的一点思路都没有

由于题目保证了坐标都是偶数，则由Shoelace公式(外积求三角形面积)知，三角形的面积一定是整数，并且是偶数

题目又要求内部点的个数为奇数，再通过Pick定理 $S=a+\frac{b}{2}-1=a-1+\frac{b}{2}$，则 $a$ 为奇数，故 $a-1$ 为偶数

进一步有：$2(S-(a-1))=b \iff b\equiv 0\pmod{4}$

于是问题就转换为求解三角形的边上格点数目为4的倍数

我们考虑 $AB$ 这条边，$A(x_1,y_1),B(x_2,y_2)$
则这条边上的格点数目一定为 $gcd(|x_1-x_2|,|y_1-y_2|)+1$，可以通过画简单的示意图得出

则

$$\begin{aligned} b&=\sum\limits_{i=1}^3(gcd(|x_i-x_{i+1}|, |y_i-y_{i+1}|)+1)-3\\ &=\sum\limits_{i=1}^3gcd(|x_i-x_{i+1}|, |y_i-y_{i+1}|)\equiv 0\pmod{4} \end{aligned}\\ x_4=x_1,y_4=y_1$$

于是，问题可以转换为$\mod 4$ 意义下，将所有的 $x, y$ 坐标都对4取模，然后求满足上式的方案数

又由于 $x,y$ 都是偶数，所以 $x,y\equiv 0\ or\ 2\pmod4$

所以模4意义下的坐标一共也就4种，可以直接枚举出3个坐标，然后判断是否满足上式，统计答案，就OK了

时间复杂度 $O(N+4^3)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int to[4][2] = {
	{0, 0}, {2, 0}, {0, 2}, {2, 2}
};
int calc(int i, int j) {
	if (abs(to[i][0] - to[j][0]) == 2 || abs(to[i][1] - to[j][1]) == 2) {
		return 2;
	}
	return 0;
}
int C(int n, int m) {
	if (m == 2) {
		return n * (n-1) / 2;
	} else {
		return n * (n-1) * (n-2) / 6;
	}
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vii cnt(4, vi(4));
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		cnt[x%4][y%4]++;
	}
	int ans = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = i; j < 4; j++) {
			for (int k = j; k < 4; k++) {
				int b = (calc(i, j) + calc(j, k) + calc(k, i)) % 4;
				if (b == 0) {
					if (i == j && j == k) {
						ans += C(cnt[to[i][0]][to[i][1]], 3);
					} else if (i == j || j == k) {
						int same = (i == j) ? i : j;
						int diff = i + j + k - same*2;
						ans += C(cnt[to[same][0]][to[same][1]], 2) * cnt[to[diff][0]][to[diff][1]];
					} else {
						ans += cnt[to[i][0]][to[i][1]] * cnt[to[j][0]][to[j][1]] * cnt[to[k][0]][to[k][1]];
					}
				}
			}
		}
	}
	cout << ans << '\n';
	return 0;
}