本想着要做四道的，结果第三题也做不出来......

A

好题目。

输入一个数 $n$, 求 $n$ 的奇数因子多还是偶数因子多。

乍一看还是没有什么头绪的，似乎是个数论题。数据范围有 $10^{18}$, 又有 $10^5$ 个询问，根号的做法显然不行， 只有 $\mathcal O(1)$ 和 $\log_2$ 的做法能过了。

我们知道偶因子就是带有 $2$ 因子的因子(废话)，那奇数因子的数量就是去掉所有带有 $2$ 因子的因子数啦。我们记 $k$ 是 $n$ 去掉所有 $2$ 因子后剩下的数，因为 $k | n$, 所以 $k$ 的因子也是 $n$ 的因子。

来构造偶数因子，设有 $x$ 个 $2$, 那么每个奇数因子都可以乘上 $1...x$ 个 $2$ 变成偶因子，所以偶因子的数量就是 $x$ 乘上 $k$ 的因子数，而 $k$ 的因子数就是所有奇数因子的数量，所以 $x < 1$ 就是奇数因子多， $x = 1$ 就是一样多， $x > 1$ 就是偶数因子多。

B

输入序列 $A$, 求所有 $A$ 的子序列最大值和最小值积的和。

若一个最大值和最小值确定了，则中间的取不取都可以，所以可以想到排个序，然后答案就是

$\sum_{i=1}^{n-1} \sum_{j=i+1}^n a_j \times a_i \times 2^{j-i-1} + \sum_{i=1}^n a_i^2$

后面一部分非常好求，考虑前面一部分怎么求。

$a_i$ 和 $j$ 无关，可以提到前面来。 式子变成了

$\sum_{i=1}^{n-1} \left( a_i\sum_{j=i+1}^n a_j \times 2^{j-i-1}\right)$

只要考虑如何快速求 $\sum_{j=i+1}^n a_j \times 2^{j-i-1}$ 就可以了。

可以预处理出 $j=1$ 的结果，然后每次只需要把 $a_i$ 减掉，后面的一堆东西除以 $2$ 就好了。

感觉还是很好的题。

C

求长度为 $n$, 每个数都不超过 $m$ 的，后一个数是前一个数的倍数的序列个数。

把半个小时过了两题之后，我就把剩下的时间都花在这题上了。

开始以为不能重复，所以直接算一下就好了，一看样例发觉不对。

一看这个 $2\times 10^ 5$ 的数据就想到是 $n\sqrt n$ 的做法，但能一下想到的只有一个 $n^2$ 状态， $\sqrt n$ 转移的糟糕 dp, 这个 dp 显然没有前途，因为状态一枚举就超时了。

又因为一个数后面能跟几个和它在 $n$ 以内的倍数个数有关，所以想到了数论分块，企图优化这个状态，但这还是一条死路，因为状态虽然可以，但转移做不到 $\mathcal O(1)$, 因为转移可以到很多块中，$\texttt{It's another dead end.}$(飞友知道我在说什么)

然后放弃了 dp 的想法，转而观察性质，未果。比赛就结束了。

来看正确做法

其实注意到最初的想法，如果不能重复会怎么样，那就好做了，因为长度枚举一个最后值， 长度肯定不能超过 $\log_2 m$ (因为从两倍开始), 不然铁定超啊。

再考虑如何用这个得到最后的答案。

其实很简单，解决重复，只要把不重复的在 $n$ 中的几个位置放上，然后剩下的都用相同的填上就可以了。

$f_{i,j}$ 是长度为 $i$ 的，最后一个为 $j$ 的，各不相同的方案数。

答案就是 $\sum C_{n-1}^{i-1} \times f_{i,j}$

代码如下。

#include <cstdio>
#include <algorithm>
#define int long long
const int M = 200005, p = 998244353;
int n, m, f[20][M], fac[M], inv[M], ans;
int Pow(int a, int b) {
	int an = 1;
	while(b) {
		if(b & 1) an = an * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return an;
}
int C(int n, int m) {
	if(n < m) return 0;
	return fac[n] * inv[m] % p * inv[n-m] % p;
}
void init(int n) {
	fac[0] = 1;
	for(int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % p;
	inv[n] = Pow(fac[n], p-2);
	for(int i = n; i >= 1; i--) inv[i-1] = inv[i] * i % p;
}
signed main() {
	scanf("%lld%lld", &n, &m);
	init(n);
	for(int i = 1; i <= m; i++) f[1][i] = 1;
	for(int i = 1; i <= 18; i++) 
		for(int j = 1; j <= m; j++)
			for(int k = 2*j; k <= m; k += j)
				f[i+1][k] = (f[i+1][k] + f[i][j]) % p;
	for(int i = 1; i <= std::min(18ll, n); i++)	
		for(int j = 1; j <= m; j++)
			ans = (ans + f[i][j] * C(n-1, i-1)) % p;
	printf("%lld", ans);
	return 0;
}

后记

$4$ 月 $10$ 日有 AGC, 但恐怕又打不了了呜呜。

其实第三题这想法听了后也不是很难，好好练习，下次加油吧。