Gym102441
总览
| 题号 | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 完成情况 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
A. Template for Search
给定由小写字母、字符
*和?组成的字符串 \(s\)，其中*可以被替换成任意串（包括空串），?可以被替换成任意字符，求 \(s\) 可以表示成的最短回文串。\(1 \leq |s| \leq 500\)。
设 \(dp[l][r]\) 表示 \(l \dots r\) 能组成的最短回文串，有三种转移：
- \(s_l\) 匹配 \(s_r\)
- \(s_l = *\) 匹配右边一段
- \(s_r = *\) 匹配左边一段
B. Redistribution of Digits
C. Partial Sums
\(n \times m\) 矩阵列 \(\{A_k\}\) 满足递推关系 \[ A_k[i, j] = \sum_{u = 1}^i\sum_{v = 1}^jA_{k-1}[u, v] \bmod 2 \]
给出 \(A_0\)，求 \(\{A_k\}\) 的最小循环节。
\(1 \leq n \times m \leq 10^6\)
递推关系是二维前缀和。数列 \(a_n\) 做 \(k\) 次前缀和的结果是 \[ a'_n = \sum_{i = 1}^na_i\binom{n - i + k - 1}{n - i} \] 这个式子可以这样推导，初始为 \(i\) 每步可以加一个非负值，走 \(k\) 步，求 \(i\) 到 \(n\) 的路径数，等价于 \(x_i+x_{i+1}+\dots+x_{n}=k, x_i, x_{i+1}, \dots, x_{n-1} \geq 0, x_n \geq 1\)，用隔板法可得答案为 \(\dbinom{n - i + k - 1}{n - i}\)。
二维相互独立，所以 \[ A_k[i, j] = \sum_{u, v}A_0[u, v]\binom{i - u + k - 1}{i - u}\binom{j - v + k - 1}{j - v} \bmod 2 \]
由卢卡斯定理，当 \(k = 2^{d_0} > n\) 时，\(\binom{i - u + k - 1}{i - u} \equiv 1 \pmod 2\)，所以循环节是 \(2^{d_0}\) 的因子。
枚举循环节 \(k = 2^d\)，由卢卡斯定理 \(\binom{i - u + k - 1}{i - u} \equiv 1 \pmod 2\) 当且仅当 \(i - u = t \times 2^d\)，即 \(u = i - 2^dt\)，用二维前缀和可以 \(O(nm)\) 验证。
复杂度 \(O(nm\log(nm))\)。
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> a(n);
for (int i = 0; i < n; i++) {
a[i].resize(m);
std::string s;
std::cin >> s;
for (int j = 0; j < m; j++) a[i][j] = s[j] - '0';
}
auto b = a;
for (int k = 1; ; k <<= 1) {
if ([&]{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
b[i][j] = a[i][j];
if (i >= k) b[i][j] ^= b[i - k][j];
if (j >= k) b[i][j] ^= b[i][j - k];
if (i >= k && j >= k) b[i][j] ^= b[i - k][j - k];
if (b[i][j] ^ a[i][j]) return false;
}
return true;
}()) {
return std::cout << k << "\n", 0;
}
if (k > n && k > m) assert(false);
}
return 0;
}D. Lis on Circle
\(n\) 个人顺时针围成一圈，第 \(i\) 个人手上有 \(m_i\) 个数 \(a_1, a_2, \dots, a_{m_i}\)，从 1 开始顺时针进行游戏，轮到一个人时他可以选择跳过，也可以出一个数，但这个数必须比之前的人出的数大。不能有连续超过 \(k\) 个人跳过，求最多能出多少数。
\(0 \leq n, \sum m_i \leq 10^5, 0 \leq a_i \leq 10^9\)。
按数从小到大dp，设 \(dp[i]\) 表示最后一个数是 \(i\) 出的，最多出了多少数，转移是区间取 \(\min\) 和单点赋值，线段树维护即可。
注意没有数的极端情况。
#include <bits/stdc++.h>
#define perr(a...) fprintf(stderr, a)
#define dbg(a...) perr("\033[32;1m"), perr(a), perr("\033[0m")
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(1e5 + 5);
PII max[N << 2];
#define ls o << 1
#define rs o << 1 | 1
void update(int o, int l, int r, int x, PII y) {
smax(max[o], y);
if (l == r) return;
int m = l + r >> 1;
x <= m ? update(ls, l, m, x, y) : update(rs, m + 1, r, x, y);
}
PII ask(int o, int l, int r, int x, int y) {
if (l > r || r < x || l > y) return {-1e9, -1};
if (x <= l && r <= y) return max[o];
int m = l + r >> 1;
return std::max(ask(ls, l, m, x, y), ask(rs, m + 1, r, x, y));
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, k;
std::cin >> m >> k;
std::vector<PII> a;
for (int i = 1; i <= m; i++) {
int t, x;
std::cin >> t;
while (t--) {
std::cin >> x;
a.emplace_back(x, i);
}
}
n = a.size();
if (!n) return std::cout << "0\n", 0;
std::sort(a.begin(), a.end());
for (auto &[x ,y] : max) x = -1e9, y = -1;
std::vector<PII> f(n, PII(-1e9, -1));
update(1, 0, m, 0, {0, -1});
for (int i = 0, j = 0; i < n; i++) {
for (; j < i && a[j].first < a[i].first; j++) {
update(1, 0, m, a[j].second, {f[j].first, j});
}
f[i] = std::max(ask(1, 0, m, a[i].second - k - 1, a[i].second - 1), ask(1, 0, m, a[i].second - k - 1 + m, m));
f[i].first++;
assert(f[i].second < i);
}
std::vector<int> ans;
for (int i = std::max_element(f.begin(), f.end()) - f.begin(); i >= 0 && f[i].first >= 1; i = f[i].second) ans.emplace_back(i);
std::reverse(ans.begin(), ans.end());
std::cout << ans.size() << "\n";
for (int i : ans) {
std::cout << a[i].second << " " << a[i].first << "\n";
}
return 0;
}E. Very Simple Sum
给定数列 \(a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n\)，求 \[ \sum_{1\leq x, y, z, w \leq n}(a_x+a_y+a_z+a_w)^{b_x\oplus b_y \oplus b_z \oplus b_w} \bmod 998244353 \]
\(1 \leq n \leq 10^5, 1 \leq a_i, b_i \leq 500\)。
设 \(cnt[i][j]\) 表示 \(i^j\) 项的个数，二维卷积 \(C[n][m] = \sum_{x + y = n, z \oplus w = m}A[x][z]\times B[y][w]\)，分别用 \(FFT, FWT\) 计算即可。
复杂度 \(O(ab\log(ab))\)。
#include <bits/stdc++.h>
template <class T>
inline void readInt(T &w) {
char c, p = 0;
while (!isdigit(c = getchar())) p = c == '-';
for (w = c & 15; isdigit(c = getchar());) w = w * 10 + (c & 15);
if (p) w = -w;
}
constexpr int P(998244353), G(3);
inline int&inc(int &x, int y) { return (x += y) >= P ? x -= P : x; }
inline int sum(int x, int y) { return x + y >= P ? x + y - P : x + y; }
inline int sub(int x, int y) { return x - y < 0 ? x - y + P : x - y; }
inline int fpow(int x, int k = P - 2) {
int r = 1;
for (; k; k >>= 1, x = 1LL * x * x % P)
if (k & 1) r = 1LL * r * x % P;
return r;
}
using Polynom = std::vector<int>;
std::vector<int> w;
void getOmega(int k) {
w.resize(k);
w[0] = 1;
int base = fpow(G, (P - 1) / (k << 1));
for (int i = 1; i < k; i++) w[i] = 1LL * w[i - 1] * base % P;
}
void dft(int *a, int n) {
assert((n & n - 1) == 0);
for (int k = n >> 1; k; k >>= 1) {
getOmega(k);
for (int i = 0; i < n; i += k << 1) {
for (int j = 0; j < k; j++) {
int y = a[i + j + k];
a[i + j + k] = (1LL * a[i + j] - y + P) * w[j] % P;
inc(a[i + j], y);
}
}
}
}
void dft(Polynom &a) { dft(a.data(), a.size()); }
void idft(int *a, int n) {
assert((n & n - 1) == 0);
for (int k = 1; k < n; k <<= 1) {
getOmega(k);
for (int i = 0; i < n; i += k << 1) {
for (int j = 0; j < k; j++) {
int x = a[i + j], y = 1LL * a[i + j + k] * w[j] % P;
a[i + j] = sum(x, y), a[i + j + k] = sub(x, y);
}
}
}
for (int i = 0, inv = P - (P - 1) / n; i < n; i++) a[i] = 1LL * a[i] * inv % P;
std::reverse(a + 1, a + n);
}
void idft(Polynom &a) { idft(a.data(), a.size()); }
void fwt(Polynom &a) {
int n = a.size();
assert((n & n - 1) == 0);
for (int k = 1; k < n; k <<= 1)
for (int i = 0; i < n; i += k << 1)
for (int j = 0, x, y; j < k; j++) {
x = a[i + j], y = a[i + j + k];
inc(a[i + j], y);
a[i + j + k] = sum(x, P - y);
}
}
void ifwt(Polynom &a) {
int n = a.size();
auto shift = [](int &x) { x = x & 1 ? x + P >> 1 : x >> 1; };
for (int k = n >> 1; k; k >>= 1)
for (int i = 0; i < n; i += k << 1)
for (int j = 0, x, y; j < k; j++) {
x = a[i + j], y = a[i + j + k];
shift(inc(a[i + j], y));
shift(a[i + j + k] = sum(x, P - y));
}
}
int main() {
int n;
readInt(n);
std::vector<int> a(n), b(n);
for (int &x : a) readInt(x);
for (int &x : b) readInt(x);
std::vector<Polynom> c(512, Polynom(2048));
for (int i = 0; i < n; i++) c[b[i]][a[i]]++;
for (auto &v : c) dft(v);
for (int j = 0; j < 2048; j++) {
Polynom d(512);
for (int i = 0; i < 512; i++) d[i] = c[i][j];
fwt(d);
for (int i = 0; i < 512; i++) d[i] = 1LL * d[i] * d[i] % P * d[i] % P * d[i] % P;
ifwt(d);
for (int i = 0; i < 512; i++) c[i][j] = d[i];
}
for (auto &v : c) idft(v);
int ans = 0;
for (int i = 0; i < 512; i++)
for (int j = 0; j < 2048; j++)
ans = (ans + 1LL * c[i][j] * fpow(j, i)) % P;
std::cout << ans << "\n";
return 0;
}F. Random XOR
给定 \(a_1, a_2, \dots, a_n\)，随机从中选取一些数的异或和为 \(s\)，求 \(s^2\) 的期望，对 \(10^9+7\) 取模。
\(n \leq 10^5\)。
设 \(s = \sum_{i\geq 0}b_i2^i\)，则 \[ \begin{aligned} s^2 &= \sum_{i, j}b_ib_j2^{i+j}\\ E(s^2) &= \sum_{i, j}P(b_i \And b_j)2^{i+j} \end{aligned} \]
\(P(b_i \And b_j)\) 表示 \(b_i, b_j\) 同时为 \(1\) 的概率，可以 \(O(n)\) 计算。
复杂度 \(O(n \log^2(P))\)。
#include <bits/stdc++.h>
using LL = long long;
using PII = std::pair<int, int>;
constexpr int P(1e9 + 7);
int fpow(int x, int k = P - 2) {
int r = 1;
for (; k; k >>= 1, x = 1LL * x * x % P) {
if (k & 1) r = 1LL * r * x % P;
}
return r;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, t, m;
std::cin >> n >> t >> m;
m = 1LL * t * fpow(m) % P;
std::vector<int> a(n);
for (int &x : a) std::cin >> x;
int ans = 0;
for (int i = 0, x = 1; i <= 30; i++, x <<= 1)
for (int j = 0, y = 1; j <= 30; j++, y <<= 1) {
std::array<int, 4> p;
p[0] = 1, p[1] = 0, p[2] = 0, p[3] = 0;
for (int &x : a) {
int v = (x >> i & 1) << 1 | (x >> j & 1);
p = {
static_cast<int>((1LL * p[v ^ 0] * m + 1LL * p[0] * (1 - m)) % P),
static_cast<int>((1LL * p[v ^ 1] * m + 1LL * p[1] * (1 - m)) % P),
static_cast<int>((1LL * p[v ^ 2] * m + 1LL * p[2] * (1 - m)) % P),
static_cast<int>((1LL * p[v ^ 3] * m + 1LL * p[3] * (1 - m)) % P)
};
}
ans = (ans + 1LL * p[3] * x % P * y) % P;
}
std::cout << (ans + P) % P << "\n";
return 0;
}G. Sum of Distances in Cactus
给定一棵边权为 1 的点仙人掌，求两点间最短路之和。
\(n \leq 10^5\)。
对每条边算贡献，对于每个环计算 \(\sum_{i,j} s_is_j\min(|i-j|, len - |i-j|)\)，前缀和优化即可。
#include <bits/stdc++.h>
#define perr(a...) fprintf(stderr, a)
#define dbg(a...) perr("\033[32;1m"), perr(a), perr("\033[0m")
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(1e5 + 5);
std::vector<int> g[N];
int n, in[N], low[N], cnt, fa[N], siz[N];
LL ans;
void dfs(int x) {
in[x] = low[x] = ++cnt;
siz[x] = 1;
for (int y : g[x]) {
if (y == fa[x]) continue;
if (!in[y]) {
fa[y] = x;
dfs(y);
siz[x] += siz[y];
smin(low[x], low[y]);
} else {
smin(low[x], in[y]);
}
if (low[y] > in[x]) {
ans += 1LL * (n - siz[y]) * siz[y];
}
}
for (int y : g[x]) {
if (fa[y] == x || in[y] < in[x]) continue;
std::vector<LL> a, b;
int p = 0;
for (int i = y; i != x; i = fa[i]) {
a.push_back(siz[i] - p);
p = siz[i];
}
a.push_back(n - p);
b.push_back(0);
assert(*std::min_element(a.begin(), a.end()) > 0);
assert(std::accumulate(a.begin(), a.end(), 0) == n);
for (int i = 1, n = a.size(); i < n; i++) {
LL a1 = a[i - 1], a2 = 0, b1 = b[i - 1], b2 = 0;
if (i - n / 2 > 0) a1 -= a2 = a[i - n / 2 - 1], b1 -= b2 = b[i - n / 2 - 1];
ans += (a1 * i - b1 + a2 * (n - i) + b2) * a[i];
b.push_back(b[i - 1] + i * a[i]);
a[i] += a[i - 1];
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int m;
std::cin >> n >> m;
while (m--) {
int x, y;
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
dfs(1);
std::cout << ans << "\n";
return 0;
}H. Not A + B
签到题。
I. Cutting
给一个整数，每次操作将这个数从中间切成两半，然后替换为差的绝对值，直到最后，求最终的最小值以及操作过程。
\(0 \leq x \leq 10^12\)。
搜索，对于 \(10^7\) 内的状态可以记忆化，大的状态数不多。
#include <bits/stdc++.h>
using LL = long long;
using PR = std::pair<int, LL>;
PR &get(LL i) {
static PR f[10000000];
static std::map<LL, PR> g;
return i < 10000000 ? f[i] : g[i];
}
template <class T>
inline int smin(T &x, T y) {
return y < x ? x = y, 1 : 0;
}
PR dfs(LL i) {
if (i < 10) return PR(i, 0);
auto &v = get(i);
if (v.first) return v;
v = {10, 0};
for (LL x = 10; i / x; x *= 10) {
auto j = i / x - i % x;
if (j < 0) j = -j;
if (j && smin(v.first, dfs(j).first)) v.second = j;
}
return v;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
LL x;
scanf("%lld", &x);
std::vector<LL> v;
for (LL o = x; o; o = dfs(o).second) v.push_back(o);
printf("%d ", (int)v.size());
for (LL x : v) printf("%lld ", x);
printf("\n");
}
return 0;
}J. Paternity Testing
\(n\) 个节点的有根树，\(q\) 次询问区间 \([l, r]\) 中满足 \(l \leq i, j \leq r, i \in subtree_j\) 的数对 \((i, j)\) 的个数。
\(n, q \leq 50000\)，强制在线。
考虑求不满足条件的个数，容易发现条件为两个子树不交，所以跑一下dfs序转化为 \(in[i] > out[j]\)。
如果只有一次询问，把 \(l\dots r\) 分别按 \(in,out\) 排序后双指针扫描即可。
分块，设块长为 \(T\)，对于节点 \(i\) 分别用双指针扫描预处理出每块中 \(in[i] > out[j]\) 和 \(out[i] < in[j]\) 的 \(j\) 的个数 \(g[i][b], h[i][b]\)，复杂度 \(O(n\log n + \frac{n^2}{T})\)。
然后预处理块与块之间的区间答案，\(ans[u][v] = \sum_{i = l}^{r} \sum_{j = u}^v g[i][j]\)，用前缀和可以做到 \(O(\frac{n^2}{T})\)。
对于每一次询问，区间分成两个部分：中间连续的块和两边的散点。
块之间的贡献已经预处理，散点自己的贡献可以双指针求出，散点和块的贡献可以根据 \(g, h\) 的前缀和计算，复杂度 \(O(T\log T)\)。
总复杂度 \(O(n \log n + \frac{n^2}{T} + qT\log T)\)，取 \(T = \frac{n}{\sqrt{q}}\) 可过。
#include <bits/stdc++.h>
#define perr(a...) fprintf(stderr, a)
#define dbg(a...) perr("\033[32;1m"), perr(a), perr("\033[0m")
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(5e4 + 5);
std::vector<int> g[N], h[N];
int in[N], out[N];
void dfs(int x) {
static int cnt;
in[x] = ++cnt;
for (int y : g[x]) dfs(y);
out[x] = cnt;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n;
for (int i = 2, x; i <= n; i++) {
std::cin >> x;
g[x].push_back(i);
}
std::cin >> q;
dfs(1);
int t = n / sqrt(q), m = (n - 1) / t + 1;
std::vector<int> pin(n), pout;
std::iota(pin.begin(), pin.end(), 1);
pout = pin;
auto cmp = [](int *p) {
return [p](int i, int j) {
return p[i] < p[j];
};
};
std::sort(pin.begin(), pin.end(), cmp(in));
std::sort(pout.begin(), pout.end(), cmp(out));
auto block = [&](int i) { return (i - 1) / t; };
std::vector<int> cnt(m);
for (int i = 0, j = 0; i < n; i++) {
int x = pin[i];
for (; out[pout[j]] < in[x]; j++) cnt[block(pout[j])]++;
g[x] = cnt;
}
for (auto &x : cnt) x = 0;
for (int i = n - 1, j = i; i >= 0; i--) {
int x = pout[i];
for (; out[x] < in[pin[j]]; j--) cnt[block(pin[j])]++;
h[x] = cnt;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < m; j++) g[i][j] += g[i][j - 1];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < m; j++) h[i][j] += h[i][j - 1];
}
std::vector<std::vector<LL>> sum(m), iBlockAns(m);
for (int i = 0; i < m; i++) {
sum[i].resize(n + 1);
for (int j = 1; j <= n; j++) sum[i][j] = g[j][i] + sum[i][j - 1];
}
for (int i = 0; i < m; i++) {
iBlockAns[i].resize(i + 1);
int r = i == m - 1 ? n : i * t + t;
LL now = 0;
for (int j = i, l = i * t + 1; j >= 0; j--, l -= t) {
for (int k = l; k < l + t && k <= r; k++) {
now += g[k][i];
}
iBlockAns[i][j] = now;
if (j) iBlockAns[i][j] -= sum[j - 1][r] - sum[j - 1][l - 1];
}
}
LL ans = 0;
while (q--) {
int l, r;
std::cin >> l >> r;
l = (l ^ ans) % n + 1;
r = (r ^ ans) % n + 1;
if (l > r) std::swap(l, r);
ans = 1LL * (r - l + 1) * (r - l) / 2 + r - l + 1;
int bl = block(l), br = block(r);
pin.clear();
if (bl == br) {
for (int i = l; i <= r; i++) pin.push_back(i);
} else {
for (int i = l, k = std::min(bl * t + t, n); i <= k; i++) pin.push_back(i);
for (int i = br * t + 1; i <= r; i++) pin.push_back(i);
}
pout = pin;
std::sort(pin.begin(), pin.end(), cmp(in));
std::sort(pout.begin(), pout.end(), cmp(out));
for (int i = 0, j = 0; i < pin.size(); i++) {
while (out[pout[j]] < in[pin[i]]) j++;
ans -= j;
}
if (bl + 1 <= br - 1) {
bl++, br--;
ans -= iBlockAns[br][bl];
for (int i : pin) {
ans -= g[i][br] - g[i][bl - 1];
ans -= h[i][br] - h[i][bl - 1];
}
}
std::cout << ans << "\n";
}
return 0;
}K. Chess Positions
最后修改于 2021-08-19