「闲话随笔」超级大豆成绩消失

「闲话随笔」超级大豆成绩消失

点击查看目录

目录

• 「闲话随笔」超级大豆成绩消失
  • 超级加倍大豆
  • 消失
  • P3270 [JLOI2016] 成绩比较

这类标题一个优势是保持抽象的同时依然可以方便的翻出需要的文章 .

没活了 . 但是又好久没更鲜花了，感觉一周年凑够十篇都费劲啊！遂写点题解 .

HE 初赛分数排名（zip），可以看看，感谢 APJ 老师打表找规律导论教我怎么用 .csv .

超级加倍大豆

为啥是大豆啊？因为骚老师路过看到了这篇文章然后念了一遍题目名字「超级加倍」 .

考虑一个类似于 Kruskal 重构树的树上笛卡尔树 . 既满足原树上两点 \(u, v\) 之间路径的最小/最大编号分别是两棵新树中两者的 LCA .

假设我们建出来了这两棵树，那么满足条件的一对点 \((x, y)\) 在新树上的 LCA 一定分别是点 \(x\) 和点 \(y\)，这个可以 DFS 序加树状数组维护 .

考虑建树，序列上建笛卡尔树的一种方式是将区间最大值作为根，左右儿子分别为左右区间（没栈快，但也挺对的）. 树上比较类似，以最大值为例，选编号最大的点作为根，然后递归子树，并与子树的新根连边 . 递归比较麻烦，所以可以从小到大遍历点，每次连上原树上和它相连且编号更小的点，使用并查集维护比较方便 .

点击查看代码

const ll N = 2e6 + 10;namespace BIT {class BIT {public: ll n;private:ll b[N];inline ll lowbit (ll x) { return x & -x; }public:inline void Update (ll x, ll y) {while (x <= n) b[x] += y, x += lowbit (x);return;}inline ll Query (ll x) {ll sum = 0;while (x) sum += b[x], x -= lowbit (x);return sum;}};
}namespace SOLVE {ll n, fa[N], tot, dfn[N][2], ans;std::vector <ll> tu[N], mntr[N], mxtr[N];BIT::BIT tr;inline ll rnt () {ll x = 0, w = 1; char c = getchar ();while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();return x * w;}ll Find (ll x) { return fa[x] == x ? x : fa[x] = Find (fa[x]); }void DFS1 (ll u) {dfn[u][0] = ++tot;far (v, mxtr[u]) DFS1 (v);dfn[u][1] = tot;return;}void DFS2 (ll u) {ans += tr.Query (dfn[u][1]) - tr.Query (dfn[u][0] - 1);tr.Update (dfn[u][0], 1);far (v, mntr[u]) DFS2 (v);tr.Update (dfn[u][0], -1);return;}inline void In () {tr.n = n = rnt (), rnt ();_for (i, 2, n) {ll fa = rnt ();tu[i].emplace_back (fa);tu[fa].emplace_back (i);}return;}inline void Solve () {_for (i, 1, n) fa[i] = i;_for (i, 1, n) {far (j, tu[i]) {if (i < j) continue;ll fu = Find (i), fv = Find (j);if (fu != fv) {mxtr[fu].emplace_back (fv);fa[fv] = fu;}}}_for (i, 1, n) fa[i] = i;for_ (i, n, 1) {far (j, tu[i]) {if (i > j) continue;ll fu = Find (i), fv = Find (j);if (fu != fv) {mntr[fu].emplace_back (fv);fa[fv] = fu;}}}DFS1 (n), DFS2 (1);return;}inline void Out () {printf ("%lld\n", ans);return;}
}

消失

为方便，\(p_{\texttt{A}}\leftarrow \frac{p_{\texttt{A}}}{p_{\texttt{A}} + p_B}, p_B\leftarrow \frac{p_B}{p_{\texttt{A}} + p_B}\) .

设 \(f_{i, j, k}\) 表示前 \(i\) 个点最后剩下 \(j\) 个 A，\(k\) 个 B .

转移：

\[f_{i, j, k} = \begin{cases} f_{i - 1, j - 1, k} &s_i = \texttt{'A'}\\ f_{i - 1, 0, k - 1} + \sum_{1}^{cnt_{\texttt{A}}}p_{\texttt{A}}^l f_{i - 1, l, k - 1} &s_i = \texttt{'B'}, j = 0\\ \sum_{l = j}^{cnt_{\texttt{A}}}p_{\texttt{A}}^{l - j}p_{\texttt{B}} f_{i - 1, j - 1, k} &\text{otherwise}\\ \end{cases} \]

前缀和优化做到 \(O(n^3)\) . 能不能再给力一点啊？

瓶颈在于要同时存 A 和 B 的数量，能不能只考虑一种字符数量，分开求？

可以，但是不知道如何合并 .

观察发现末态长成一个 BB...BBAA...AA 的形式，就是说总存在一个断点 \(p\)，它前面的串只剩下 B，后面的串只剩下 A .

那么枚举这个断点 \(p\)，合并前面的 B 的结果和后面的 A 的结果即可 .

具体的，考虑设 \(f_{i, j}\) 当前断点 \(p\) 之前到 \(i\) 最终剩下 \(j\) 个 B 点，有转移方程：

\[f_{i, j} = \begin{cases} p_{\texttt{A}}f_{i + 1, j} + p_{\texttt{B}}f_{i, j + 1} &s_i = \texttt{'A'}\\ f_{i + 1, j - 1} &\text{otherwise} \end{cases} \]

对点 \(p\) 之后的 A 点设一个 \(g\)，转移同理 . 初始状态是 \(f_{p, 1} = 1\) .

每个断点对答案的贡献是此时的 \(f_{1, c_\texttt{B}}\times g_{n, c_\texttt{A}}\) .

现在还是 \(O(n^3)\)，考虑进一步优化 .

不难发现不管断点 \(p\) 如何变化，每个状态的转移方程与最终态都不变，只有初始态变化 .

考虑一个忘了从哪里看到的但是好像还挺典的一个 trick，把最终态与初始态交换，转移方程反过来推一遍 . 正确性感性理解还挺对的，你可以想象成一个 DAG 反向建边 .

这样的话只用推一次 \(f\) 和 \(g\)，时间复杂度 \(O(n^2)\) .

是不是通过阅读实现来理解思路会导致程序长得和贺的一样 .

点击查看代码

const ll N = 5010, P = 998244353;
namespace SOLVE {ll n, pa, pb, ca, cb, f[N], g[N], F[N], G[N], ans;char s[N];inline ll rnt () {ll x = 0, w = 1; char c = getchar ();while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();return x * w;}inline ll FastPow (ll a, ll b) {ll ans = 1;while (b) {if (b & 1) ans = ans * a % P;a = a * a % P, b >>= 1;}return ans;}inline void In () {n = rnt ();scanf ("%s", s + 1);pa = rnt (), pb = rnt (), ca = rnt (), cb = rnt ();return;}inline void Solve () {ll tmp_inv = FastPow (pa + pb, P - 2);pa = pa * tmp_inv % P, pb = pb * tmp_inv % P;f[cb] = 1, F[0] = f[0];_for (i, 1, n) {if (s[i] == 'B') _for (j, 0, n) f[j] = f[j + 1];else {f[0] = 0;_for (j, 1, n) f[j] = (f[j] * pa + f[j - 1] * pb) % P;}F[i] = f[0];}g[ca] = 1, G[n + 1] = g[0];for_ (i, n, 1) {if (s[i] == 'A') _for (j, 0, n) g[j] = g[j + 1];else {g[0] = 0;_for (j, 1, n) g[j] = (g[j] * pb + g[j - 1] * pa) % P;}G[i] = g[0];}_for (i, 0, n) ans = (ans + F[i] * G[i + 1]) % P;return;}inline void Out () {printf ("%lld\n", ans);return;}
}

P3270 [JLOI2016] 成绩比较

看到这个「恰好」就比较套路的放上二项式反演：设 \(f(k)\) 表示恰好 \(k\) 个人被碾压，\(g(x)\) 表示钦定 \(k\) 个人被碾压 .

不难得到反演式子:

\[g(k) = \sum_{i = k}^{n}\dbinom{i}{k}f(i)\Leftrightarrow f(k) = \sum_{i = k}^{n}(-1)^{i - k}\dbinom{i}{k}g(i) \]

考虑求 \(g(k)\)，有式子：

\[g(k) = \dbinom{n - 1}{k}\prod_{i = 1}^{m}\sum_{s = 1}^{U_i}\dbinom{n - k - 1}{R_i - 1}s^{n - R_i}(U_i - s)^{R_i - 1} \]

简单解释：选出 \(k\) 个人被钦定，对于每一科考虑枚举 D 神的分数，在没被钦定的 \(n - k - 1\) 个人中选出 \(R_i - 1\) 个人作为分数比 D 神高的人，然后可以知道每个人分数的可能数，其积为每个人的分数的总可能数 .

这样复杂度是基于值域的，考虑展开后面的依托：

\[\begin{aligned}&\sum_{s = 1}^{U_i}\dbinom{n - k - 1}{R_i - 1}s^{n - R_i}(U_i - s)^{R_i - 1}\\ =&\sum_{s = 1}^{U_i}\dbinom{n - k - 1}{R_i - 1}s^{n - R_i}\sum_{j = 0}^{R_i - 1}\dbinom{R_i - 1}{j}U_i^{j}(-1)^{R_i - 1 - j}s^{R_i - 1 - j}\\ =&\dbinom{n - k - 1}{R_i - 1}\sum_{j = 0}^{R_i - 1}(-1)^{R_i - 1 - j}\dbinom{R_i - 1}{j}U_i^{j}\sum_{s = 1}^{U_i}s^{n - j - 1}\\ =&\dbinom{n - k - 1}{R_i - 1}h(i) \end{aligned} \]

这个 \(h(i)\) 部分只与 \(i\) 有关所以单独提出来进行预处理，现在和值域有关的部分只剩下了后面的自然数幂和，这样就可以拉插或伯努利数处理了 .

但是我不会拉插也不会伯努利数，咋整呀？

答案是用扰动法可以得到自然数幂和的一个递推式：

\[S_{t}(n) = \sum_{k = 1}^{n}k^{t} = \frac{(n + 1) ^ {t + 1} - \sum_{j = 0}^{t - 1}\dbinom{t + 1}{j}S_j(n)}{(t + 1)} \]

我写这个是为了让你知道我代码里有啥，最好还是用拉插的，不然别人也不知道你在干什么 .

这样可以 \(O(mR^2) = O(n^3)\) 预处理出所有的 \(h(i)\)，然后把它带回原式：

\[f(k) = \sum_{i = k}^{n}(-1)^{i - k}\dbinom{i}{k}\dbinom{n - 1}{i}\prod_{j = 1}^{m}\dbinom{n - i - 1}{R_j - 1}h(j) \]

可以 \(O(n^2)\) 算出 .

点击查看代码

#include <bits/stdc++.h>
#define lowb(a, r, x) lower_bound(a + 1, a + r + 1, x) - a
#define uppb(a, r, x) upper_bound(a + 1, a + r + 1, x) - a
#define _for(i, a, b) for (ll i = a; i <= b; ++i)
#define for_(i, a, b) for (ll i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd ll mid = (l + r) >> 1
#define NO nullptr
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <ll, ll> pll;
const ll N = 110, P = 1e9 + 7;
namespace SOLVE {ll n, m, k, U[N], R[N], s[N], h[N], fac[N], inv[N], invf[N], ans;inline ll rnt () {ll x = 0, w = 1; char c = getchar ();while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();return x * w;}inline ll FastPow (ll a, ll b) {ll ans = 1;while (b) {if (b & 1) ans = ans * a % P;a = a * a % P, b >>= 1;}return ans;}inline void PreC (ll n) {fac[0] = fac[1] = 1, inv[0] = inv[1] = 1, invf[0] = invf[1] = 1;_for (i, 2, n) {fac[i] = fac[i - 1] * i % P;inv[i] = (P - P / i) * inv[P % i] % P;invf[i] = invf[i - 1] * inv[i] % P;}return;}inline ll C (ll n, ll m) {return fac[n] * invf[m] % P * invf[n - m] % P;}inline void PreS (ll n, ll t) { //  Sum of powers of natural numbers.s[0] = n + 1;_for (i, 1, t) {s[i] = 0;_for (j, 0, i - 1) s[i] = (s[i] + C (i + 1, j) * s[j]) % P;s[i] = (FastPow (n + 1, i + 1) - s[i] + P) * FastPow (i + 1, P - 2) % P;}return;}inline void In () {n = rnt (), m = rnt (), k = rnt ();_for (i, 1, m) U[i] = rnt ();_for (i, 1, m) R[i] = rnt ();return;}inline void Solve () {PreC (n);ll w = 1;_for (i, 1, m) {PreS (U[i], n);ll w = 1;for_ (j, R[i] - 1, 0) {h[i] = (h[i] + w * C (R[i] - 1, j) * FastPow (U[i], j) % P * s[n - 1 - j]) % P;w *= -1;}}_for (i, k, n) {ll g = C (n - 1, i);_for (j, 1, m) g = g * C (n - i - 1, R[j] - 1) % P * h[j] % P;ans = (ans + w * C (i, k) * g % P + P) % P;w *= -1;}return;}inline void Out () {printf ("%lld\n", ans);return;}
}
int main () {
#ifndef ONLINE_JUDGEfreopen ("data.in", "r", stdin);
#endifSOLVE::In ();SOLVE::Solve ();SOLVE::Out ();return 0;
} /**/