AtCoder Regular Contest 185 总结

hhhqx / 2024-10-21 / 原文

总结

D 题待补

一题都不会，爽了。

今天这些题的套路，我一个都没见过，涨见识了......

A 题没看出来可能是赛时耐心不够，不应该一直在那里光看样例找规律。

E 题我已经简单转化完了，而且最近写过欧拉反演。数学题并不一定那么明显，其实看到 $\gcd$ 就应该有意识去推一推式子。

C 题，最近练了的 FFT 和 NTT，结果还是白给。这些求一个解的题可能需要先求出方案数。

B 题，这题需要先看出一个最优序列，然后再判断。

D 题我直接去套随机游走这题的递推式，结果退出来了个不可做。期望还得练。

[ARC185A] mod M Game 2

A 和 B 每个人手上都有 $n$ 张牌。点数分别为 $1$ 到 $n$。A 先手。每次打出一张牌（一张牌不能重复使用），如果某人打出牌后，总和是 $m$ 的倍数，这个人就输了。

若牌出完了还没人输，则 A 胜。

多组数据，$T \le 10^5$ 且 $1 \le n < m \le 10^9$。

做法

因为 $n < m$，如果一人手上有两张牌，他就不可能输。

两人至少一人手上有两张牌，我们可以忽略他们具体是如何操作的，因为一定有一种方法达到这种状态（毕竟两人聪明绝顶）。

只用关心最后的状态。

由于 A 先把自己的牌打完，如果 B 想要赢，就必须最后剩一个 $x$，满足 $n(n+1)-x$ 是 $m$ 的倍数。

代码

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using PII = pair<int, int>;

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	int T; cin >> T;
	while(T--){
		LL n, m; cin >> n >> m;
		cout << (1 <= n * (n + 1) % m && n * (n + 1) % m <= n ? "Bob" : "Alice") << "\n";
	}
	return 0;
}

[ARC185B] +1 and -1

一个序列 $A$，每次操作可以选择 $1 \le i < j \le n$ 然后 $A_i$ 加一、$A_j$ 减一。

问能否通过若干次操作使得 $A$ 变为非降序列。注意是问能否。

多组数据，$T \le 2 \cdot 10^5$ 且 $\sum{n} \le 2 \cdot 10^5$ 且 $0 \le A_i \le 10^9$。

做法

设 $s = \sum{A_i}$。注意无论如何操作 $s$ 都不会变。

我们需要找到一个最优的序列，不仅满足不降，而且不能继续操作。

若 $s \bmod n = 0$，则序列就是 $n$ 个 $\frac{s}{n}$。

拓展一下，则序列就是前面 $n - s \bmod n$ 个 $\left\lfloor \frac{s}{n} \right\rfloor$，而后面是 $s \bmod n$ 个 $\left\lfloor \frac{s}{n} \right\rfloor + 1$。

最优序列得到了，然后就是要判断能否达成这个最优序列。设最优序列为 $B$。

也就是需要每个 $1 \le r \le n$ 都满足 $\sum\limits_{i=1}^{r}{B_i - A_i} \ge 0$。

代码

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using PII = pair<int, int>;

const int MAXN = 2e5 + 3;

int n;
LL a[MAXN], b[MAXN];

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	int T; cin >> T;
	while(T--){
		cin >> n;
		LL s = 0;
		for(int i = 1; i <= n; i++){
			cin >> a[i], s += a[i];
		}
		for(int i = 1; i <= n; i++) b[i] = s / n;
		for(int i = n - s % n + 1; i <= n; i++){
			b[i]++;
		}
		bool ooo = 1;
		s = 0;
		for(int i = 1; i <= n; i++){
			s += b[i] - a[i];
			ooo &= s >= 0;
		}
		cout << (ooo ? "Yes\n" : "No\n"); 
	}
	return 0;
}

[ARC185C] Sum of Three Integers

一个序列 $A$ 和一个整数 $X$。

输出一个 $1 \le i < j < k \le n$ 满足 $A_i + A_j + A_k = X$。

$3 \le n \le 10^6$ 且 $1 \le A_i \le X \le 10^6$。

做法

输出一个有些困难，先试着算一些方案数。

$f[x]$ 表示数字 $x$ 的出现次数。$g[x]$ 表示多少个 $1\le i < j \le n$ 满足 $A_i+A_j = x$。

这 $g[x]$ 的式子根卷积几乎一模一样！有 $2 \cdot g[x] = \sum\limits_{i + j = x}{f[i] \cdot f[j]} - f[\frac{x}{2}] [x \bmod 2 = 0]$。

求 $g$ 可以用 NTT（其实这题不需要使用大模数，因为这题只是判存在性）。

最后总方案数有 $3 \cdot ans = \sum\limits_{i=1}^{n}{(g[X - A_i] - f[X - 2 \cdot A_i] + [3 \cdot A_i = X])}$

如果存在 $i$ 满足 $\frac{g[X - A_i] - f[X - 2 \cdot A_i] + [3 \cdot A_i = X]}{3} \ge 1$，就确定一个位置了，然后可以直接枚举剩余的两个中的一个。

点击查看代码

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const LL mod = 998244353, gen = 3, igen = 332748118;

LL qpow(LL A, LL B){
	LL ret = 1;
	while(B > 0){
		if(B & 1) ret = ret * A % mod;
		A= A * A % mod, B >>= 1;
	}
	return ret;
}

namespace NTT{
	const int BR = 4e6 + 3;
	int r[BR], po;
	LL a[2][BR];
	void Doit(int op, int _op){
		for(int i = 0; i < (1ll << po); i++){
			if(i < r[i]) swap(a[op][i], a[op][r[i]]);
		}
		for(int l = 1; l < (1ll << po); l <<= 1){
			LL w = qpow((_op > 0 ? gen : igen), (mod - 1) / (l * 2));
			int L = l * 2;
			for(int j = 0; j < (1ll << po); j += L){
				LL sum = 1;
				for(int k = 0; k < l; k++){
					LL x = a[op][j + k], y = sum * a[op][j + k + l] % mod;
					a[op][j + k] = (x + y) % mod, a[op][j + k + l] = (x - y + mod) % mod;
					sum = sum * w % mod;
				}
			}
		}
	}
	vector<LL> MUL(vector<LL> A, vector<LL> B){
		int ln = A.size() - 1, lm = B.size() - 1;
		for(po = 0; (1ll << po) <= ln + lm; po++);
		for(int i = 0; i < (1ll << po); i++){
		  r[i] = 0;
		  for(int x = i, y = 0; y < po; y++, x /= 2) r[i] = r[i] * 2 + x % 2;
    }
	  for(int i = 0; i <= ln; i++) a[0][i] = A[i];
		for(int i = 0; i <= lm; i++) a[1][i] = B[i];
		Doit(0, 1), Doit(1, 1);
		for(int i = 0; i < (1ll << po); i++) a[0][i] = a[0][i] * a[1][i] % mod;
		Doit(0, -1);
		LL in = qpow((1ll << po), mod - 2);
		vector<LL> C;
		for(int i = 0; i <= ln + lm; i++) C.push_back(a[0][i] * in % mod);
		return C;
	}
}

const int MAXN = 1e6 + 3, V = 1e6;

int n, X, a[MAXN];
LL f[MAXN], g[MAXN];
vector<int> ans;

void out(){
	sort(ans.begin(), ans.end());
	for(int x : ans) cout << x << " ";
	exit(0);
}

int main(){
  //ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> X;
	for(int i = 1; i <= n; i++){
		cin >> a[i], f[a[i]]++;
	}
	vector<LL> A;
	LL i2 = qpow(2, mod - 2), i3 = qpow(3, mod - 2);
	for(int i = 0; i <= V; i++) A.push_back(f[i]);
	A = NTT::MUL(A, A);
	for(int i = 1; i <= V; i++){
		g[i] = A[i];
		if(i % 2 == 0) g[i] = (g[i] - f[i / 2] + mod) % mod; 
		g[i] = g[i] * i2 % mod;
	}
	for(int i = 1; i <= n; i++){
		LL w = (g[X - a[i]] - f[max(0, X - 2 * a[i])] + (3 * a[i] == X) + mod) % mod;
		w = w * i3 % mod;
		if(w != 0){ 
			ans.push_back(i), f[a[i]]--;
			for(int j = 1; j <= n; j++){ if(i == j) continue;
				f[a[j]]--;
				if(f[max(0, X - a[i] - a[j])]){
					ans.push_back(j);
					for(int k = 1; k <= n; k++){
						if(a[k] + a[i] + a[j] == X && k != i && k != j) ans.push_back(k), out();
					}
					ans.pop_back();
				}
				f[a[j]]++;
			}
			ans.pop_back(), f[a[i]]++;
		}
	}
	cout << -1;
	return 0;
}

[ARC185D] Random Walk on Tree

一颗大小 $n * m + 1$ 的树，视 $0$ 为根节点，它挂了 $n$ 条含 $m$ 个节点的链。

根节点已经绘制，P 初始位于根节点，每次等概率走向一个连接的节点（父亲和儿子），到一个点后该点就被绘制了，求期望多少步使得全部都被绘制。

[ARC185E] Adjacent GCD

直接去看原题面吧。。。

做法

简单转化可以得到 $ans_i = 2ans_{i - 1} + \sum\limits_{j=1}^{i-1}{\gcd(a_i, a_j) 2^{j-1}}$。

看到 $\gcd$ 就要敏感，考虑欧拉反演，具体推式子看 https://www.luogu.com.cn/article/bql8wgwu 。

设 $g_{i,d} = \sum\limits_{x=1}^{i-1}{2^{x-1} [d | a_x]}$

$\sum\limits_{j=1}^{i-1}{\gcd(a_i, a_j) 2^{j-1}}$ 就等于 $\sum\limits_{d | a_i}{\varphi(d) g_{i,d}}$。

$g$ 可以动态维护，然后就做完了。

代码

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const LL mod = 998244353;
const int MAXN = 5e5 + 3;

int F[MAXN];
LL Fi(int x){
	if(F[x] > 0) return F[x];
	int _x = x; 
	F[_x] = x;
	for(int j = 2; j * j <= x; j++){
		if(x % j == 0) F[_x] = F[_x] / j * (j - 1);
		while(x % j == 0) x /= j;
	}
	if(x > 1) F[_x] = F[_x] / x * (x - 1);
	return F[_x];
}

int n, a[MAXN];
LL g[MAXN];

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	LL ans = 0, po = 1;
	for(int i = 1; i <= n; i++){
		vector<int> vt;
		for(int j = 1; j * j <= a[i]; j++){
			if(a[i] % j == 0){
				vt.push_back(j);
				if(j != a[i] / j) vt.push_back(a[i] / j);
			}
		}
		ans = ans * 2 % mod;
		for(int d : vt){
			ans += g[d] * Fi(d) % mod, ans %= mod;
		}
		
		cout << ans << "\n";

		for(int d : vt){
			g[d] += po % mod, g[d] %= mod;
		}
		po = po * 2ll % mod;
	}
	return 0;
}