哭了，还是写不了 Ex 的题解，因为不会

A - N-choice question

题意

给定 \(a,b\) 和序列 \(\{c_n\}\)，求 \(a+b\) 在 \(c\) 中的下标。

分析

直接记录一下 \(pos_{c_i}=i\) 就薄纱了。

code

int main() {
	n = read(), a = read() + read();
	for (int i = 1; i <= n; i++) p[read()] = i;
	write(p[a]);
}
// I love WHQ!

B - Same Map in the RPG World

题意

给定 \(n\times m\) 的矩阵 \(A,B\)，问能不能通过水平和竖直的整体平移使 \(A^\prime=B\)。

分析

推一下，当位移为 \((x,y)\) 时，\(A_{i,j}\) 会跑到 \(A_{(i+x)\bmod n,(j+y)\bmod m}\)，暴力判断即可。

code

int main() {
	n = read(), m = read();
	for (int i = 0; i < n; i++) scanf("%s", a[i]);
	for (int i = 0; i < n; i++) scanf("%s", b[i]);
	for (int r = 0; r < n; r++) for (int c = 0; c < m; c++) {
		bool fl = 1;
		for (int i = 0; i < n && fl; i++) for (int j = 0; j < m && fl; j++) 
			if (b[(i + r) % n][(j + c) % m] != a[i][j]) fl = 0;
		if (fl) return puts("Yes"), 0;
	}
	puts("No");
}
// I love WHQ!

C - Cross

题意

不好描述，自己看吧！

分析

直接对于每一个点，暴力向外拓展即可，注意细节和审题。

code

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (s[i][j] != '#') continue;
			int k = 0;
			while (s[i + k][j + k] == '#' && s[i + k][j - k] == '#' && s[i - k][j + k] == '#' && s[i - k][j - k] == '#') ++k;
			++ans[k - 1];
		}
	}
	for (int i = 1; i <= min(n, m); i++) writesp(ans[i]);
}
// I love WHQ!

D - AABCC

题意

有多少个小于 \(n\) 的整数，可以被表示成 \(a^2bc^2,a,b,c\in\mathbb P,a<b<c\) 的形式。

\(n\le10^{12}\)。

分析

首先可以将式子化为 \(x=(ac)^2b\)，所以不难看出 \(a<b<c\le10^6\)。

于是考虑线性筛预处理出 \([1,10^6]\) 内的质数数量前缀和，每个数质因子的数量和最大质因子，枚举 \(ab\) 即可，复杂度 \(\mathcal O(\sqrt n)\)。

code

inline void seive (int N) {
	for (int i = 2; i <= N; i++) {
		pre[i] = pre[i - 1];
		if (!vis[i]) pr[++tot] = i, ++pre[i], c[i] = 1, v[i] = i;
		for (int j = 1; j <= tot && i * pr[j] <= N; j++) {
			vis[i * pr[j]] = 1, c[i * pr[j]] = c[i] + 1, v[i * pr[j]] = max(v[i], pr[j]);
			if (i % pr[j] == 0) break;
		}
	}
}

signed main() {
	seive(1000000);
	n = read();
	for (int i = 6; i * i < n; i++) 
		if (c[i] == 2 && i != v[i] * v[i]) {
			int l = min((LL)v[i] - 1, n / (i * i));
			if (l > i / v[i]) ans += pre[l] - pre[i / v[i]];
		}
	write(ans);
}
// I love WHQ!

E - Dice Product 3

题意

初始时有一个 \(x=1\)，每次扔骰子随机选出一个 \([1,6]\) 的整数 \(p\)，让后令 \(x\gets xp\)。问结果恰好是 \(n\) 的期望 \(\bmod 998244353\)。

\(2\le n\le10^{18}\)。

分析

考虑可以设计一个很基础的 dp，设 \(f_{x}\) 表示扔到 \(x\) 的期望，不难列出转移：

发现有环，稍微移一下项就有：

发现这个转移的问题在于 \(x\) 中有很多废物，因为 \(x\) 只能包含因子 \(2,3,5\)。所以改一下 dp，换成 \(f_{i,j,k}\) 表示扔到 \(2^i3^j5^k\) 的期望，转移大同小异，不写了。

code

int main() {
	n = read();
	while (n % 2 == 0) ++p, n /= 2;
	while (n % 3 == 0) ++q, n /= 3;
	while (n % 5 == 0) ++r, n /= 5;
	if (n > 1) return puts("0"), 0;
	f[0][0][0] = 1;
	for (int i = 0; i <= p; i++) {
		for (int j = 0; j <= q; j++) {
			for (int k = 0; k <= r; k++) {
				if (i) add(f[i][j][k], iv5 * f[i - 1][j][k] % mod);
				if (j) add(f[i][j][k], iv5 * f[i][j - 1][k] % mod);
				if (i && j) add(f[i][j][k], iv5 * f[i - 1][j - 1][k] % mod);
				if (i > 1) add(f[i][j][k], iv5 * f[i - 2][j][k] % mod);
				if (k) add(f[i][j][k], iv5 * f[i][j][k - 1] % mod);
			}
		}
	}
	write(f[p][q][r]);
}
// I love WHQ!

F - More Holidays

题意

给定只包含 x 和 o 的长度为 \(n\) 的字符串 \(S\) 和整数 \(m,k\)。将 \(m\) 个 \(S\) 首尾拼接得到字符串 \(T\)，问通过将 \(T\) 中 \(k\) 个 x 变成 o 能得到的最长 o 连续子段长度。

分析

因为是直接复制 \(S\) 得到 \(T\)，所以可以认为答案对应的子段起点一定在第一个 \(S\) 内。于是考虑二分答案，判断 \([i,i+mid-1]\) 这个区间内的 x 数量是否超过 \(k\)，预处理 x 数量前后缀和就好了。

code

inline int calc (int l, int r) {
	int B = (r - 1) / n;
	if (r <= n) return pre[r] - pre[l - 1];
	return pre[n] * (B - 1) + suf[l] + pre[r - B * n];
}

inline bool check (LL mid) {
	for (int i = 1, j = i + mid - 1; i <= n && j <= n * m; i++, j++) 
		if (calc(i, j) <= k) return 1;
	return 0;
}

signed main() {
	n = read(), m = read(), k = read();
	scanf("%s", s + 1);
	for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + (s[i] == 'x');
	for (int i = n; i; i--) suf[i] = suf[i + 1] + (s[i] == 'x');
	LL l = 1, r = n * m, mid, res = 0;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) l = mid + 1, res = mid;
		else r = mid - 1;
	}
	write(res);
}
// I love WHQ!

G - P-smooth number

题意

求有多少小于等于 \(n\) 的整数，满足其最大的质因子不超过 \(P\)。

\(n\le10^{16},2\le P\le100\)。

分析

考虑到质数的数量应该是很小的，所以最后组成的时候应该数量不会太多，关键在于 \(2\) 对应的次数会比较大。有由于有 \(\lfloor\dfrac{n}{bc}\rfloor=\lfloor\dfrac{\lfloor\dfrac{n}{b}\rfloor}{c}\rfloor\)，所以考虑暴力 dfs，最后到 \(2\) 的时候用 __lg 来算。让后可以考虑进一步的优化，可以通过记忆化搜索的方式来解决，其实还可以再进一步进行一些底层优化，可以通过预处理 dp 的方式处理出较小的情况的答案，大概阈值取到 \(2^{18}\) 的时候就已经跑的飞快了。极限数据 dfs 递归了 \(28353155\) 次，还是相当宽裕的。

code

inline void dfs (LL m, int p) {
	if (m < N) return ans += f[p][m], void();
	if (!p) return ans += __lg(m) + 1, void();
	dfs(m, p - 1);
	if (m >= pr[p]) dfs(m / pr[p], p);
}

int main() {
	n = read(), lim = pos[read()];
	for (int i = 1; i < N; ++i) f[0][i] = __lg(i) + 1;
	for (int i = 1; i < lim; ++i)
		for (int j = 0, l = 0; j < N; j += pr[i], ++l)
			for (int k = j; k < j + pr[i] && k < N; ++k)
				f[i][k] = f[i][l] + f[i - 1][k];
	dfs(n, lim - 1);
	write(ans);
}
// I love WHQ!