哭了，还是写不了 Ex 的题解，因为不会
A - N-choice question
题意
给定 \(a,b\) 和序列 \(\{c_n\}\)，求 \(a+b\) 在 \(c\) 中的下标。
分析
直接记录一下 \(pos_{c_i}=i\) 就薄纱了。
code
const int maxn(2e5 + 500);
int n, a, p[maxn];
int main() {
n = read(), a = read() + read();
for (int i = 1; i <= n; i++) p[read()] = i;
write(p[a]);
}
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
const int maxn(35);
int n, m;
char a[maxn][maxn], b[maxn][maxn];
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");
}
C - Cross
题意
不好描述，自己看吧！
分析
直接对于每一个点，暴力向外拓展即可，注意细节和审题。
code
const int maxn(5005);
int n, m, ans[maxn];
char s[maxn][maxn];
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]);
}
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
const int maxn(1e6 + 500);
LL n, ans;
int pr[maxn], tot, v[maxn], c[maxn], pre[maxn];
bool vis[maxn];
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);
}
E - Dice Product 3
题意
初始时有一个 \(x=1\)，每次扔骰子随机选出一个 \([1,6]\) 的整数 \(p\)，让后令 \(x\gets xp\)。问结果恰好是 \(n\) 的期望 \(\bmod 998244353\)。
\(2\le n\le10^{18}\)。
分析
考虑可以设计一个很基础的 dp，设 \(f_{x}\) 表示扔到 \(x\) 的期望，不难列出转移：
\[f_{x}=\dfrac{1}{6}\sum_{i=1}^6[i|x]f_{\frac{x}{i}}
\]
发现有环，稍微移一下项就有：
\[f_{x}=\dfrac{1}{5}\sum_{i=2}^6[i|x]f_{\frac{x}{i}}
\]
发现这个转移的问题在于 \(x\) 中有很多废物，因为 \(x\) 只能包含因子 \(2,3,5\)。所以改一下 dp，换成 \(f_{i,j,k}\) 表示扔到 \(2^i3^j5^k\) 的期望，转移大同小异，不写了。
code
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;
namespace IO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
inline long long read() {
char ch = gh();
long long x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
template <typename _Tp>
inline void write(_Tp x) {
static char stk[64], *top = stk;
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
do *top++ = x % 10, x /= 10;
while (x);
while (top != stk) putchar((*--top) | 48);
}
}
using IO::read;
using IO::write;
const int maxn(70), mod(998244353);
const LL iv5(598946612);
LL n;
int p, q, r, f[maxn][maxn][maxn];
inline void add (int &x, const int &y) { x += y; x > mod && (x -= mod); }
inline int ksm (int b, int k) {
int res = 1;
for (; k; k >>= 1, b = (LL)b * b % mod) if (k & 1) res = (LL)res * b % mod;
return res;
}
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
题意
给定长度为 \(n\) 的只包含 x 和 o 的字符串 \(S\)，和整数 \(m,k\)。考虑由 \(m\) 个 \(S\) 首尾拼接得到字符串 \(T\)，长度为 \(nm\)。求通过将 \(k\) 个 x 变成 o 能在 \(T\) 中得到的最长连续 o 子段长度。
分析
考虑因为是 \(S\) 首尾拼接，所以这个字段的开头可以钦定一定在第一个 \(S\) 中。于是可以考虑二分答案，问题变成判断是否存在长为 \(mid\) 的字段可以通过删除 \(k\) 个 x 得到。直接枚举开头，剩下部分通过预处理前后缀和可以轻松解决。
复杂度 \(\mathcal O(n\log n)\)。
code
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define int long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;
namespace IO {
// char ibuf[(1 << 20) + 1], *iS, *iT;
// #if ONLINE_JUDGE
// #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
// #else
#define gh() getchar()
// #endif
inline long long read() {
char ch = gh();
long long x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
template <typename _Tp>
inline void write(_Tp x) {
static char stk[64], *top = stk;
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
do *top++ = x % 10, x /= 10;
while (x);
while (top != stk) putchar((*--top) | 48);
}
}
using IO::read;
using IO::write;
const int maxn(3e5 + 500);
int n, m, k, pre[maxn], suf[maxn];
char s[maxn];
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
#include <bits/stdc++.h>
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;
namespace IO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
inline long long read() {
char ch = gh();
long long x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
template <typename _Tp>
inline void write(_Tp x) {
static char stk[64], *top = stk;
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
do *top++ = x % 10, x /= 10;
while (x);
while (top != stk) putchar((*--top) | 48);
}
}
using IO::read;
using IO::write;
const int N(1 << 16), pos[] = {0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25}, pr[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
int lim;
LL n, f[30][N], ans;
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!