当前位置: 首页 > news >正文

近期杂题

A. 出关

http://222.180.160.110:61235/contest/6462/problem/1

给定 \(s\),对于一个空串,任意利用下列三种操作,使其变为 \(s\),求最小代价:

  1. 在末尾添加字符 \(c\),代价为 \(t_{0,c}\)
  2. 复制整个字符串并粘贴在末尾,代价为 \(t_1\)
  3. 删除末尾字符,代价为 \(t_2\)

\(|s|\le 10^6\)

可以预处理出对于每个 \(i\) 结尾,最多可以复制到哪个地方,发现要求 \(z_i=lcp(s_{1\dots n},s_{i+1\dots n})\)。那么一个 \(i\) 的最远转移点 \(r_i=i+z_{i+1}\),用单调队列就能维护,会 exkmp 就能线性;

否则可以二分 + 哈希多个 log,后面也有理由偷懒用优先队列了。

#include <bits/stdc++.h>
const int p = 31;
const int mod = 998244353;
int main() {std::freopen("laozi.in", "r", stdin);std::freopen("laozi.out", "w", stdout);std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::string s;std::cin >> s;int n = (int)s.length(), t1, t2;std::vector<long long> h(n + 1), base(n + 1);std::vector<int> a(n + 1), t0(27), z(n + 1), r(n + 1);base[0] = 1ll;for (int i = 1; i <= n; ++i) {a[i] = s[i - 1] - 'a' + 1;h[i] = (h[i - 1] * p + a[i]) % mod;base[i] = base[i - 1] * p % mod;}auto gethash = [&](int l, int r) {return (h[r] - h[l - 1] * base[r - l + 1] % mod + mod) % mod;};for (int i = 1; i <= n; ++i)for (int l = 1, r = std::min(i - 1, n - i + 1), mid; l <= r; ) {mid = (l + r) >> 1;if (gethash(1, mid) == gethash(i, i + mid - 1))z[i] = mid, l = mid + 1;elser = mid - 1;}for (int i = 1; i < n; ++i)r[i] = i + std::min(i, z[i + 1]);for (int i = 1; i <= 26; ++i)std::cin >> t0[i];std::cin >> t1 >> t2;std::vector<long long> f(n + 1);std::priority_queue<std::pair<long long, int> > q;for (int i = 1; i <= n; ++i) {f[i] = f[i - 1] + t0[a[i]];for (; !q.empty() && r[q.top().second] < i; q.pop());if (!q.empty())f[i] = std::min(f[i], t1 - q.top().first - (long long)t2 * i);if (i != n)q.emplace(-(f[i] + 2ll * t2 * i), i);}std::cout << f[n] << '\n';return 0;
}

D. 非攻

http://222.180.160.110:61235/contest/6462/problem/4

给定 \(n\),对于一个 \(1\sim n\) 的排列,使用最小的交换次数使得其单增。在该前提下,定义代价为每次交换的两个数之积。对于所有 \(n!\) 个排列,计算最小代价之和。

\(n\le 10^7\)

转化成,把 \(1\sim n\) 分成无标号的若干组,每组的代价是 最小值 \(\times\) 其他元素的和,还有一个项链问题的系数,发现组间的符号是求和,考虑计算贡献。

枚举 \(i,j\) 并钦定两个同属一个环,且 \(i\) 为最小值,枚举环大小 \(s+2\),那么有:

\[\begin{aligned} res&=\sum_{i=1}^{n-1}\sum_{j=i+1}^n i\cdot j \cdot \sum_{s=0}^{n-i-1}\binom{n-i-1}s \cdot (s+1)!\cdot (n-s-2)!\\ &=\sum_{i=1}^{n-1}i\cdot \dfrac {(i+n+1)(n-i)}2 \cdot \sum_{s=0}^{n-i-1}\binom{n-i-1}s\cdot (s+1)!\cdot (n-s-2)!\\ &=\frac 12\times\sum_{i=1}^{n-1}i\cdot (i+n+1)\cdot (n-i)!\cdot\sum_{s=0}^{n-i-1}\dfrac {(s + 1)\cdot (n-s-2)!}{(n-i-1-s)!}\\ \end{aligned} \]

\(T=n-i-1\),发现我们需要快速计算 \(f_T=\sum\limits_{i=0}^T \dfrac{(i+1)\cdot (n-i-2)!}{(T-i)!}\)。记 \(m=n-2\),变形得 \(f_T=(m-T)!\cdot \sum\limits_{i=0}^{T} (i+1) \binom{m-i}{m-T}\),发现似乎可以简化,令 \(k=m-T,t=T+1\),则 \(f_T=\sum\limits_{i=1}^T i\cdot \binom {k+t-i}k\)

然后是经典的组合意义保平安环节,即从 \(k+t\) 个有标号小球中选择一条分界线,分界线左边选一个球、右边选 \(k\) 个球的方案数。发现分界线的存在很诡异,故用分界线后方的第一个球代替,在 \(t+1\) 处新建一个虚球,规定在前 \(t+1\) 个球中选两个球,并令后一个为分界线,且令前 \(t+1\) 个中的其他球为实球,就能建立双射。在分界线后再选 \(k\) 个球,容易发现直接在范围内选 \(k+2\) 个球就能满足条件,故 \(f_T=(n-T-2)!\cdot \binom{t+k+1}{k+2}\)

#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::freopen("mozi.in", "r", stdin);std::freopen("mozi.out", "w", stdout);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);
#endifint n;std::cin >> n;std::vector<long long> fac(n + 1), inv(n + 1), f(n + 1);fac[0] = inv[0] = 1ll;for (int i = 1; i <= n; ++i)fac[i] = fac[i - 1] * i % mod;auto qkp = [&](long long x, int y) {auto res(1ll);for (; y; (x *= x) %= mod, y >>= 1)if (y & 1)(res *= x) %= mod;return res;};inv[n] = qkp(fac[n], mod - 2);for (int i = n - 1; i; --i)inv[i] = inv[i + 1] * (i + 1) % mod;auto C = [&](int n, int m) {return fac[n] * inv[n - m] % mod * inv[m] % mod;};int m = n - 2;for (int T = 0; T <= n - 2; ++T) {int k = m - T, t = T + 1;f[T] = C(t + k + 1, k + 2) * fac[m - T] % mod;}auto res = 0ll;for (int i = 1; i <= n - 1; ++i)(res += (long long)i * (i + n + 1) % mod * fac[n - i] % mod * f[n - i - 1] % mod) %= mod;std::cout << res * inv[2] % mod << '\n';return 0;
}

C - Destruction of Walls

https://atcoder.jp/contests/arc203/tasks/arc203_c


D - Insert XOR

https://atcoder.jp/contests/arc203/tasks/arc203_d


A - 记忆

https://ac.nowcoder.com/acm/problem/274793

需要意识到问题是静态的,并且不能用线段树之类维护;故考虑离线下来,想办法在 LCA 处统计答案。

这个时候发现需要合并子树状态、整体异或、整体 +1,很容易想到 Trie。把 \(u\to\) LCA 的答案保存在 LCA 处,然后再用 DFS + 回溯统计 LCA \(\to v\) 的答案。想了半天没想到把上下拆开来做也是神了 😅

可能比较考验对字典树的理解?做个比喻,字典树的 id 就相当于对这个点上信息的『引用』。

字典树合并的时候可以考虑回收废弃点,不然可能有点卡。

#include <bits/stdc++.h>
const int X = 50;
const int maxn = 2e7 + 5;
long long d[maxn];
int tot, T[maxn][2], f[maxn], fa[maxn];
#define lc(p) T[p][0]
#define rc(p) T[p][1]
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
int newnode(void) {int p = ++tot;assert(p < maxn);d[p] = lc(p) = rc(p) = 0, f[p] = p;return p;
}
void pushdown(int p) {if (d[p]) {if (d[p] & 1)std::swap(lc(p), rc(p));d[p] >>= 1;if (lc(p))d[lc(p)] ^= d[p];if (rc(p))d[rc(p)] ^= d[p];d[p] = 0;}return;
}
int ins(int p, long long x) {for (int i = 0; i < X; ++i) {pushdown(p);if (!T[p][(x >> i) & 1]) {T[p][(x >> i) & 1] = newnode();fa[T[p][(x >> i) & 1]] = p;}p = T[p][(x >> i) & 1];}return p;
}
void merge(int &p, int q) {if (!q)return;if (!p) {p = q;return;}pushdown(p), pushdown(q);fa[lc(q)] = p, fa[rc(q)] = p;merge(lc(p), lc(q)), merge(rc(p), rc(q));assert(f[p] == p), assert(f[q] == q), f[q] = p;return;
}
long long ask(int p) {std::vector<int> st;for (int i = 0, j = p; i < X; ++i)st.push_back(fa[j]), j = fa[j];for (int i = 0; i < X; ++i)pushdown(st.back()), st.pop_back();long long x = 0;for (int i = 0; i < X; ++i) {x = x * 2 + (p == rc(fa[p]));p = fa[p];}return x;
}
void add(int p) {for (int i = 0; p && i < X; ++i) {pushdown(p);std::swap(lc(p), rc(p));p = lc(p);}return;
}
void del(int p) {for (int i = 0; p && i < X; ++i) {pushdown(p);std::swap(lc(p), rc(p));p = rc(p);}return;
}
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);
#endifint n, m;std::cin >> n >> m;std::vector<int> a(n + 1);for (int i = 1; i <= n; ++i)std::cin >> a[i];std::vector<std::vector<int> > g(n + 1);for (int i = 1, x, y; i < n; ++i) {std::cin >> x >> y;g[x].push_back(y), g[y].push_back(x);}std::vector<int> siz(n + 1), son(n + 1), top(n + 1), fa(n + 1), dep(n + 1);std::function<void(int)> DFS = [&](int x) {siz[x] = 1;for (auto i : g[x])if (i != fa[x]) {dep[i] = dep[x] + 1;fa[i] = x, DFS(i);siz[x] += siz[i];if (siz[i] > siz[son[x]])son[x] = i;}return;};DFS(1);DFS = [&](int x) {if (son[x])top[son[x]] = top[x], DFS(son[x]);for (auto i : g[x])if (i != son[x] && i != fa[x])top[i] = i, DFS(i);return;};top[1] = 1, DFS(1);auto askLCA = [&](int x, int y) {for (; top[x] != top[y]; x = fa[top[x]])if (dep[top[x]] < dep[top[y]])std::swap(x, y);return dep[x] < dep[y] ? x : y;};struct node { long long x; int u, v; };std::vector<node> q(m + 1);std::vector<int> id(m + 1);std::vector<long long> res(m + 1), ans(m + 1);std::vector<std::vector<int> > up(n + 1), dn(n + 1), ed(n + 1);for (int i = 1, x, u, v; i <= m; ++i) {std::cin >> x >> u >> v;q[i] = { x, u, v };up[u].push_back(i), dn[askLCA(u, v)].push_back(i), ed[v].push_back(i);}std::vector<int> rt(n + 1);DFS = [&](int x) {rt[x] = newnode();for (auto i : g[x])if (i != fa[x]) {DFS(i);merge(rt[x], rt[i]);}add(rt[x]);for (auto i : up[x])id[i] = ins(rt[x], q[i].x);d[rt[x]] ^= a[x];for (auto i : dn[x])res[i] = ask(find(id[i]));return;};DFS(1);tot = 0, rt[0] = newnode();std::fill(id.begin() + 1, id.end(), 0);DFS = [&](int x) {d[rt[0]] ^= a[x];for (auto i : dn[x])id[i] = ins(rt[0], res[i]);for (auto i : ed[x])ans[i] = ask(id[i]);add(rt[0]);for (auto i : g[x])if (i != fa[x])DFS(i);del(rt[0]);d[rt[0]] ^= a[x];return;};DFS(1);for (int i = 1; i <= m; ++i)std::cout << ans[i] << '\n';return 0;
}

B - ビーバーの会合 2 (Meetings 2)

https://www.luogu.com.cn/problem/AT_joisc2021_j

定义所求点为『局部重心』;类似树的重心,容易发现当关键点数量为奇时,只存在一个局部重心;否则,局部重心组成一条链。

即对于每一个 \(i\),需要找到一条最长链,使得其两端存在大小为 \(i\) 的子树(容易发现取后缀 max 即可得到真实答案)。使用点分治,精细实现容易做到 \(O(n\log n)\)

#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);
#endifint n;std::cin >> n;std::vector<std::vector<int> > g(n + 1);for (int i = 1, x, y; i < n; ++i) {std::cin >> x >> y;g[x].push_back(y), g[y].push_back(x);}std::vector<int> mx(n + 1), siz(n + 1), p, tag(n + 1), res(n + 1, 1);std::function<void(int, int)> DFS1 = [&](int x, int fa) {p.push_back(x);siz[x] = 1, mx[x] = 0;for (auto i : g[x])if (!tag[i] && i != fa) {DFS1(i, x);siz[x] += siz[i];mx[x] = std::max(mx[x], siz[i]);}return;};auto findrt = [&](int x) {p.clear(), DFS1(x, -1);int n = (int)p.size();for (auto i : p)if (mx[i] <= n / 2 && n - siz[i] <= n / 2)return i;assert(0);return -1;};struct node {int u1, u2, id1, id2;node(): u1(0), u2(0), id1(0), id2(0) {}void upd(int u, int id) {if (id1 == id)u1 = std::max(u1, u);else if (u >= u1)u2 = u1, id2 = id1, u1 = u, id1 = id;else if (u >= u2)u2 = u, id2 = id;return;}};std::vector<node> s(n + 1);std::function<void(int, int, int, int)> DFS2 = [&](int x, int fa, int dep, int anc) {s[siz[x]].upd(dep, anc);for (auto i : g[x])if (!tag[i] && i != fa)DFS2(i, x, dep + 1, anc);return;};std::function<void(int, int, int, int)> DFS3 = [&](int x, int fa, int dep, int anc) {int v = ((s[siz[x]].id1 == anc) ? s[siz[x]].u2 : s[siz[x]].u1);res[2 * siz[x]] = std::max(res[2 * siz[x]], dep + 1 + v);for (auto i : g[x])if (!tag[i] && i != fa)DFS3(i, x, dep + 1, anc);return;};std::function<void(int)> DFS = [&](int x) {x = findrt(x), p.clear(), DFS1(x, -1);// printf("rt = %d\n", x);for (auto i : g[x])if (!tag[i])DFS2(i, x, 1, i);for (int i = siz[x] - 1; i; --i) {s[i].upd(s[i + 1].u1, s[i + 1].id1);s[i].upd(s[i + 1].u2, s[i + 1].id2);}for (auto i : g[x])if (!tag[i])DFS3(i, x, 1, i);tag[x] = 1;for (int i = 1; i < siz[x]; ++i)s[i] = node();for (auto i : g[x])if (!tag[i])DFS(i);return;};DFS(1);for (int i = (n >> 1) * 2; i; --i)if (i + 2 <= n)res[i] = std::max(res[i], res[i + 2]);for (int i = 1; i <= n; ++i)std::cout << res[i] << '\n';return 0;
}

C - The Closest Pair

https://ac.nowcoder.com/acm/problem/262593

常规方法:考虑支配对,对于每个 \(a_i\),找到所有合法的 \(a_j\)。容易想到枚举 \(a_i\div a_j\) 来做;假设存在 \(a_k\div a_i=a_j\div a_i\)\(k>j\)

不妨设 \(a_j=K\cdot a_i+p,a_k=K\cdot a_i+q\)\((a_i,a_j),(a_i,a_k)\) 均合法当且仅当下列条件全部成立:

  • \(a_j\bmod a_i>a_k\bmod a_i\); 则 \(a_j>a_k\)
  • \(a_j\bmod a_k>a_k\bmod a_i\);又 \(p-q\ge a_j\bmod a_k\)太牛了这一步),即 \(p-q>q\iff p>2q\)

证得只关心同一个 \(a_j\div a_i\) 时的支配对数量为 \(\log n\) 级别;总对数 \(O(n\log n\ln n)\)。离线下来扫描线就行了。

对着 单点修改 区间最值 想了 1h 的单 log 做法 😰 果然小脑掉线太可怕了,第二天早上重置大脑 1s 发现自己是斯波 😓

#include <bits/stdc++.h>
const int LEN = (1 << 20);
int nec(void) {static char buf[LEN], *p = buf, *e = buf;if (p == e) {e = buf + fread(buf, 1, LEN, stdin);if (e == buf) return EOF;p = buf;}return *p++;
}
bool read(int &x) {x = 0;bool f = 0;char ch = nec();while (ch < '0' || ch > '9') {if (ch == EOF) return 0;if (ch == '-') f = 1;ch = nec();}while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = nec();}if (f) x = -x;return 1;
}
void print(int x) {if (x < 0)putchar('-'), x = -x;if (x >= 10) print(x / 10);putchar(x % 10 + '0');return;
}
void print(int x, char ch) {print(x), putchar(ch);return;
}
const int maxn = 4e6 + 5;
struct { int l, r, u[2]; } t[maxn];
#define lt (t[p].l)
#define rt (t[p].r)
int tot[2];
void add(int &p, int l, int r, int x, int v, int i) {if (!p)p = ++tot[i], t[p].u[0] = -1, t[p].u[1] = 0x3f3f3f3f;if (i == 0)t[p].u[0] = std::max(t[p].u[0], v);elset[p].u[1] = std::min(t[p].u[1], v);if (l == r)return;int mid = (l + r) >> 1;if (x <= mid)add(lt, l, mid, x, v, i);elseadd(rt, mid + 1, r, x, v, i);return;
}
int ask(int p, int l, int r, int ql, int qr, int i) {if (!p || (ql <= l && r <= qr))return t[p].u[i];int mid = (l + r) >> 1;if (qr <= mid)return ask(lt, l, mid, ql, qr, i);if (ql > mid)return ask(rt, mid + 1, r, ql, qr, i);if (i == 0)return std::max(ask(lt, l, mid, ql, qr, 0), ask(rt, mid + 1, r, ql, qr, 0));return std::min(ask(lt, l, mid, ql, qr, 1), ask(rt, mid + 1, r, ql, qr, 1));
}
#undef lt
#undef rt
int main() {
#ifndef ONLINE_JUDGEstd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);const auto stime = std::chrono::steady_clock::now();
#endifconst int m = 1e6;int rt[2] = { 0 }, n;t[0].u[0] = -1, t[0].u[1] = 0x3f3f3f3f;read(n);std::vector<int> a(n + 1);for (int i = 1; i <= n; ++i)read(a[i]);std::vector<std::vector<std::pair<int, int> > > t(n + 1);for (int i = 1; i <= n; ++i) {if (i != 1) {for (int K = a[i]; K <= m; K += a[i]) {for (int mx = std::min(a[i] - 1, m - K); ; ) {int k = ask(rt[0], 1, m, K, K + mx, 0);if (k == -1)break;t[i].emplace_back(k, a[k] - K);if (k == 1 || !(a[k] - K))break;mx = (a[k] - K - 1) / 2;}}}add(rt[0], 1, m, a[i], i, 0);}for (int i = n; i; --i) {if (i != n)for (int K = a[i]; K <= m; K += a[i])for (int mx = std::min(a[i] - 1, m - K); ; ) {int k = ask(rt[1], 1, m, K, K + mx, 1);if (k == 0x3f3f3f3f)break;t[k].emplace_back(i, a[k] - K);if (k == n || !(a[k] - K))break;mx = (a[k] - K - 1) / 2;}add(rt[1], 1, m, a[i], i, 1);}int q;read(q);std::vector<int> res(q + 1);std::vector<std::vector<std::pair<int, int> > > u(n + 1);for (int i = 1, l, r; i <= q; ++i) {read(l), read(r);if (l > r)std::swap(l, r);u[r].emplace_back(l, i);}std::vector<int> bit(n + 1, 0x3f3f3f3f);auto lowbit = [&](int x) { return x & -x; };auto add = [&](int x, int v) {for (; x <= n; x += lowbit(x))bit[x] = std::min(bit[x], v);return;};auto ask = [&](int x) {auto res = 0x3f3f3f3f;for (; x; x -= lowbit(x))res = std::min(res, bit[x]);return res;};for (int r = 1; r <= n; ++r) {for (auto [l, v] : t[r])add(n - l + 1, v);for (auto [l, i] : u[r])res[i] = ask(n - l + 1);}for (int i = 1; i <= q; ++i)print(res[i], '\n');
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}

求支配对的过程也要带 log(线段树),再加上扫描线的 3log,总共是常数比较大的 3log(卡了一个上午的常也是有了)。所以接下来讲解另一种奇技淫巧。

暴力分治:注意到对于比较长(\(len> B\))的区间,答案比较小;故考虑分治。

  • 对于长询问(\(len>B\)),从小到大枚举答案并 check;预处理某个范围(\(V\))内的 \(res\) 出现的所有位置,平衡的时候还要算上调和级数和 bit。
  • 对于短询问(\(len\le B\)),发现每次区间内暴力是 \(O(B^2q)\) 的;把询问离线下来,精细实现,利用询问的公共部分使得每一对数只被枚举一次就能达到 \(O(B^2 + Bq)\)

最优解取 \(B=333,V=483\),不自己实现一遍了。


D - 仙人掌

https://www.luogu.com.cn/problem/P3687

把边双从图中删除、问题转化为树上不交的链覆盖,使得所有链长 \(\ge 2\) 的方案数。发现由于边可以不被覆盖,常规 DP 会使得在父节点处合并时需要额外的数量维,参考树上背包,复杂度 \(O(n^2)\)

思考时会注意到两个限制可以抵消——如果认为长为 \(1\) 的链就是不被覆盖的边,覆盖所有树边,显然可以建立和合法解的双射。此时合并是非常方便的,注意到每个儿子的系数一定都参与『分步』,只需要求出『分类』的系数。这个可以预处理(和 二分图染色 这个题有点像),令 \(f_i\) 表示一个点度数为 \(i\) 时的答案,参考错排的思路,则 \(i\) 可以不参与配对,也可以乱选一个点配对,如果选中了已配对的点就令其和 \(i-1\) 交换,可以建立和合法解的双射。则 \(f_i=f_{i-1}+(n-1)f_{i-2}\)

首先需要 check 原图是否为仙人掌,顺带回忆一下连通性的知识——在 DFS 树上差分,检查是否有边被覆盖两次即可。

#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);const auto stime = std::chrono::steady_clock::now();
#endifint T;for (std::cin >> T; T--; ) {int n, m;std::cin >> n >> m;std::vector<std::vector<int> > g1(n + 1);for (int x, y; m--; ) {std::cin >> x >> y;g1[x].push_back(y), g1[y].push_back(x);}bool flag = 1;int now = 0, cnt = 0;std::vector<int> st, dfn(n + 1), low(n + 1), col(n + 1), diff(n + 1);std::function<void(int, int)> DFS = [&](int x, int fa) {st.push_back(x);dfn[x] = low[x] = ++now;for (auto i : g1[x])if (!dfn[i]) {// printf("x = %d, %d -> %d\n", x, x, i);DFS(i, x);diff[x] += diff[i];// printf("x = %d, diff[%d] += diff[%d]\n", x, x, i);low[x] = std::min(low[x], low[i]);}else if (i != fa && dfn[i] < dfn[x]) {low[x] = std::min(low[x], dfn[i]);++diff[x], --diff[i];// printf("x = %d, ++diff[%d], --diff[%d]\n", x, x, i);}if (diff[x] >= 2)flag = 0;// printf("x = %d, diff[%d] = %d\n", x, x, diff[x]);if (low[x] == dfn[x]) {++cnt;for (int p = -1; p != x; ) {p = st.back(), st.pop_back();col[p] = cnt;}}return;};DFS(1, -1);if (!flag) {std::cout << 0 << '\n';continue;}std::vector<std::vector<int> > g(n + 1);for (int i = 1; i <= n; ++i)for (auto j : g1[i])if (col[i] != col[j])g[i].push_back(j);std::vector<long long> f(n + 1), dp(n + 1);dp[0] = 1ll, dp[1] = 1ll;for (int i = 2; i <= n; ++i)dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % mod;std::vector<int> tag(n + 1);DFS = [&](int x, int fa) {f[x] = 1ll, tag[x] = 1;for (auto i : g[x])if (i != fa) {DFS(i, x);(f[x] *= f[i]) %= mod;}(f[x] *= dp[(int)g[x].size()]) %= mod;return;};auto res(1ll);for (int i = 1; i <= n; ++i)if (!tag[i])DFS(i, -1), (res *= f[i]) %= mod;std::cout << res << '\n';}
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}

E. Many Minimizations 是数学题,跳了。



无名题

背景:给定 \(n,k\),对于 \(\forall\, 1\le i\le n\),令 \(a_i=i\bmod k\),问一共有多少个本质不同的子序列?对于 \(k=1,2,\cdots,n\) 分别求出答案。


maimai

https://ac.nowcoder.com/acm/contest/66112/F

http://www.hskmm.com/?act=detail&tid=23666

相关文章:

  • 学习笔记:分拆数与 Ferrers 图
  • DDP 与全局平衡二叉树
  • 并查集 D. Shark [Codeforces Round 484(Div. 2)]
  • 实用指南:Spark核心技术解析:从RDD到Dataset的演进与实践
  • 随笔0
  • 加密算法基本原理、特点及采用场景
  • Hackersdaddy ROUGE CTF 2025 完整解题记录
  • AI元人文系列:透明推理者——下一代大模型架构设计
  • 个人随笔
  • 实用指南:1、docker入门简介
  • 调试parlant的大模型配置,最终自己动手写了g4f的模块挂载 - 教程
  • PowerShell注意点
  • 太极 - MKT
  • 题解:P12410 「知りたくなかった、失うのなら」
  • unity面向组合开发二:EC的代码实践
  • 《咳咳,未来编程大师,顶尖程序员的第一条博客》
  • CSP-JF36
  • 超越炒作:使用Agentic AI构建系统架构
  • K个节点的组内逆序调整
  • 【任务】自然语言处理——情感分析 <上>
  • 文件目录
  • 【Azure App Service】Root CA on App Service
  • QOJ #8147. Math Exam 题解
  • 10.03模拟赛t3
  • 国庆梦熊集训做题记录
  • 文件的逻辑结构
  • python 肘部法则,判点聚类分为几类,K-means聚类分析
  • AT_abc315_f [ABC315F] Shortcuts
  • 紫外UV固化太阳光模拟器的原理 - 教程
  • 每日一题