ARC185

georegyucjr / 2024-10-15 / 原文

没看的会标记出来，会了没写的不会贴代码，过了会贴代码。

A

A statement

两个人在博弈，每个人手上有$1\sim n$共$n$张牌。每次每方都可以出一张牌，如果当前所有牌的sum为$m$的倍数，那么出这牌的人输。如果到最后还是没有出现$m$的倍数过，那么Alice胜。多测。

$1\le T \le 10^5$
$1\le n, m \le 10^9$

A sol

我没想去证过，凭感觉和手模猜到的。感觉就是胜负只和Alice的最后一张牌有关系直接考虑Bob是否能够通过最后一步使得为$m$的倍数（我也不是到我在写什么）。具体的可以去看一下官方editorial。

A code

code

main() ...

	int T; read(T); rep(_, 1, T) {
		ll n, m; read(n, m);
		constexpr auto o = [&](bool &&flg) { writeln(flg ? "Bob"s : "Alice"); };
		if (m > (1 + n) * n) 
			{o(0);continue;}
		ll x = (1 + n) * n % m;
		if (x == 0 || x > n) o(0);
		else o(1);
	}

B

B statement

给定一个序列，问是否能否通过若干次操作使得序列变得不减。操作的定义是选$1\le i < j\le n$, $\text{let} \ a_i=a_i+1,a_j=a_j-1$。多测。

$1 \leq T \leq 2 \times 10^5$
$2 \leq n \leq 2 \times 10^5$
$0 \leq a_i \leq 10^9$
$\sum \limits n \leq 2\times 10^5$

B sol

首先我们发现我们如果是合法的都是可以变成前面sum%n个sum/n,n-sum%n个(sum+n-1)/n。比如$(4, 6)$，可以通过一次操作变成$(5, 5)$

然后考虑变成如上形式。我们令我们要变成的第$i$位是$b_i$，那么如果$\exist 1\le m\le n,\sum \limits_{i=1}^{m}b_i-a_i<0$，也就意味着前面减的比加的多了，显然是不合法的，因此不合法。否则合法。

B code

完整代码

	int T; read(T); rep(_, 1 ,T) {
		int n; read(n); vector<int> a(n), b(n); forall(a, [&](auto &x) { read(x); }); 
		auto sum = accumulate(ALL(a), 0LL);
		int p = n + 1 - sum % n, dv = sum / n;
		rep0(i, 0, p - 1) b[i] = dv;
		rep0(i, p - 1, n) b[i] = dv + 1;
		dbg(b);
		ll tot = 0;
		bool flg = true;
		rep0(i, 0, n) {
			tot += b[i] - a[i];
			if (tot < 0) {
				flg = false;
				break;
			}
		}
		writeln(flg ? "Yes"s : "No"s);
	}

C

C statement

给你一个长度为$n$序列$a$，询问是否存在$i, j, k$，使得

$1 < i < j < k \le n$
$a_i + a_j + a_k = m$($m$给定)
$3 \leq n \leq 10^6$
$1 \leq x \leq 10^6$
$1 \leq a_i \leq X$

C sol

这个题场上看了5min胡了，好像有点类似官方做法？

套路的我们想到枚举一个数是多少（比如枚举$j$），然后就转化成了询问是否存在一对$i, k$，使得$a_i + a_k = m - a_j$

我们姑且不管他不能相等，发现就是$x + y = z$的形式，发现可以直接卷积。在发现后面的哪个也是卷积形式。一开始的想法是直接记录一个数有没有出现过，直接卷积。

但是发现一个问题，$i\not = j \not = k$，也就是说只记录是否出现是假的。于是直接考虑记录出现次数，然后卷积，减去会有相同的数量，详见代码。

提一嘴，我在每一次卷积后把$>m$的部分都erase掉了，不然极大概率会T。我扔掉还是跑了2991ms。可能跟我没卡常有关？

C code

完整代码

核心代码：


// head
# include <atcoder/all>

vector<ll> f;

int n, m;
vector<vector<int> > p;

ll C2(ll x) { return x * (x - 1) / 2; } 

signed main() {
  // ios_base ::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	read(n, m);
	f.resize(m + 1);
	p.resize(m + 1);
	rep(i, 1, n, x) read(x), f[x]++, p[x].eb(i);
	auto g = atcoder::convolution_ll(f, f);
	if (SZ(g) > m + 1) 
		g.erase(begin(g) + m + 1, end(g));
	rep(x, 0, m / 2) if (SZ(p[x])) g[x * 2] -= SZ(p[x]), chkmax(g[x * 2], 0);
	auto h = atcoder::convolution_ll(g, f);
	if (SZ(h) > m + 1) 
		h.erase(begin(h) + m + 1, end(h));	
	rep(x, 0, m / 3) if (SZ(p[x])) h[x * 3] -= g[x * 2] * 2;
	if (h[m] == 0) 
		return writeln("-1"s), 0;
	vector<int> cur(m + 1);
	vector<int> pos(3, 0);
	rep(i, 0, m)
		if (f[i] && g[m - i]) {
			pos[0] = ++cur[i];
			rep(j, 0, m - i) 
				if (f[j] && f[m - i - j]) {
					pos[1] = ++cur[j];
					pos[2] = ++cur[m - i - j];
					if (cur[i] <= SZ(p[i]) && cur[j] <= SZ(p[j]) && cur[m - i - j] <= SZ(p[m - i - j])) {
						vector<int> tans = {p[i][pos[0] - 1], p[j][pos[1] - 1], p[m - i - j][pos[2] - 1]};
						sort(ALL(tans));
						writeall(tans);
						return 0;
					} else {
						--cur[j], --cur[m - i - j];
					}
				}
			--cur[i];
		}
	writeln("-1"s);

#if defined(LOCAL) && !defined(CPH)
  std::cerr << "Spend Time : " << clock() * 1. / CLOCKS_PER_SEC * 1e3 << " ms \n";
#endif
  return 0;
}

D

D statement

一棵树，根节点将n条长度为m的链连接起来，从根节点走，随机会走到相邻节点，求走遍所有点的概率。

$1 \leq n, m \leq 2 \times 10^5$

D sol

开了个小挂，找了个经典结论。

hint1

发现n条长度为m的链是相同的，分开考虑

hint2

长度为m+1的链（算根节点）平均的往返次数为$m^2$

证明

转化问题，变成给你一个$[0,n]$的数轴，在$[1, n - 1]$的时候你都可以随意向左或右走，$0$的时候只能走右边，$n$的时候不能往右。令$f_x$表示当前坐标在x时的期望步数。不难发现$f_x=\frac{f_{x-1}+f_{x+1}}{2}+1$

考虑移向。$f_{i+1}-f_i=f_{i}-f_{i-1}-2$。令$g_i=f_i-f_{i-1}$。那么就变成了$g_{i+1}=g_{i}-2$。特殊的，由于$f_0=f_1+1$,所以$g_1=1$。则$g_x=-2x+1$。那么$f_i=f_{i-1}+g_i=f_{i}+1-2i$

移向得$f_{i-1}=f_{i}+2i-1$。求和发现$f_0=\sum \limits_{i=1}^{n}(2i-1)=n^2$
$\mathcal{Q.E.D}$

考虑只有$m=1$的时候答案是什么。第k次选显然的有$\frac{n-k+1}{n}$的概率会选到一个从未选择过的点，那么反之期望次数就是$\frac{n}{n-k+1}$。那么$m=1$时答案就是$2\sum \limits_{i=1}^{n}\frac{n}{i}-1$,由于时往返，并且都走过就不用再走最后一步了，所以减1。自然的，最后的答案是$m=1$的答案$\times m^2$，由hint2得。

综上，答案是$((2\sum \limits_{i=1}^{n}\frac{n}{i})-1)\times m^2$

D code

完整代码

# include <atcoder/modint>
using mint = atcoder :: modint998244353;
// in main
	int n, m;
	read(n, m);
	mint ans = 0;
	rep0(i, 0, n) 
		ans += mint(n - i).inv();
	writeln(((ans * n * 2 - 1) * m * m).val());

E

E statement

定义一个序列的价值$val(B_1,B_2,...,B_{len})=\sum \limits_{i=1}^{len-1}gcd(B_i,B_{i+1})$

对于$m=1...n$,求$1...m$的所有子序列的价值的和。

$1 \leq n \leq 5 \times 10^5$
$1 \leq a_i \leq 10^5$

E sol

这个题赛后推式子没退出来，还是cly告诉我欧拉反演，遂穿了。

考虑移动一位的影响，无论这一位是否选定$1\sim i - 1$的f都会$\times 2$, 然后再加上第$i$位取的贡献。考虑上一次取的是$j$,贡献位$gcd(a_i,a_j)\times 2^j$

thus

\[f_i = 2f_{i - 1} + \sum \limits_{j = 1}^{i - 1} 2^j gcd(a_i, a_j) \]

套路的会想到莫反，实际上这个题要用到欧拉反演。

反演的基本式是：$\sum \limits_{d | n} \varphi(d) = n$

这里证略。考虑把gcd当作$n$，展开：

$f_i = 2f_{i - 1} + \sum \limits_{j = 1}^{i - 1} 2^j (\sum \limits_{d | gcd(a_i, a_j)} \varphi(d))$

$\ \ \ = 2f_{i - 1} + \sum \limits_{j = 1}^{i - 1} 2^j (\sum \limits_{d | a_i} \varphi(d)[d|a_j])$

$\ \ \ = 2f_{i - 1} + \sum \limits_{d | a_i} \varphi(d) \sum \limits_{j = 1}^{i - 1} 2^j [d|a_j]$

后面这个东西是好维护的，在转移$f$的时候维护一个$g$即可。详见代码。

E code

好像哪个地方计了两次还是怎么样，反正写完发现都是两倍懒得找原因了直接$/2$了

完整代码


constexpr int N = 5e5 + 5;
constexpr int V = 1e5;

int n, a[N];

# include <atcoder/modint>
using mint = atcoder::modint998244353;

mint dp[N], num[N], pw2[N];
int p[N], prime[N], pcnt = 0, phi[N];
vector<int>muls[V + 5], divs[V + 5];

void init() {
	p[1] = 1; phi[1] = 1;
	rep(i, 2, V) {
		if (!p[i])p[i] = i, prime[++pcnt] = i, phi[i] = i - 1;
		for (int j = 1; j <= pcnt && i * prime[j] <= V; ++j) {
			p[i * prime[j]] = prime[j];
			if (i % prime[j] == 0) {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			phi[i * prime[j]] = phi[i] * (prime[j] - 1);
		}
	}
}

signed main() {
	// ios_base ::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	init(); pw2[0] = 1; rep(i, 1, N - 5) pw2[i] = pw2[i - 1] + pw2[i - 1];
	read(n);
	rep(i, 1, V) rep(j, 1, V / i) muls[i].eb(i * j), divs[i * j].eb(i);
	rep(i, 1, n) read(a[i]);
	auto mx = *max_element(a + 1, a + n + 1);
	rep(i, 1, n) {
		dp[i] = 2 * dp[i - 1];
		if (i != 1) {
			for (auto fc : divs[a[i]])
				dp[i] += phi[fc] * num[fc];
		}
		if (i < n) {
			for (auto fc : divs[a[i]])
				num[fc] += pw2[i];
		}
	}
	rep(i, 1, n)writeln((dp[i] / 2).val());

#if defined(LOCAL) && !defined(CPH)
	std::cerr << "Spend Time : " << clock() * 1. / CLOCKS_PER_SEC * 1e3 << " ms \n";
#endif
	return 0;
}