Contest: AtCoder Beginner Contest 223(ABC223)
被自己蠢哭了A不解释B蠢哭了，还需要什么最小表示法...直接暴力转出来排序即可。C搞心态了先试着前后同时跳，然后跳到一个地方停。然而非常难写。然后开始二分时间，发现精度根本不够。然后发现停的时间直接算出来，只要遍历每一段看是跳完还是跳剩下的时间能跳多少，然后顺便计算路程即可。D一个数要在另一个数之前在排列中出现，这样就是拓扑排序确定出现次数吧..要求字典序最小的话就优先队列就可以了。E题解写的真好：solF这个 F 不比 E 简单？转成一个括号序列了之后，相当于每次交换两个括号就是单点修改，询问就是检查该区间每一个前缀和是否 $> 0$ 并且区间和 $=0$ 。然后我 SB 地写了一个暴力线段树每次进叶节点算前缀...其实只需要改成线段树维护前缀和就行了...G感觉又是一个换根 DP，但是还是先考虑一下对每个点做一下的普通 DP 吧。设 $f_{u,0/1}$ 表示以 $u$ 为根的子树的最大匹配，且 $0/1$ 分别表示 $fa_u \to u$ 这条边选还是不选。转移：$f_{u,0} = \sum\limits_{v \in son_u} \max {(f_{v,0}, f_{v,1})}$， $f_{u,1} = \sum\limits_{v \in son_u} \max {(f_{v,0}, f_{v,1})} + [\exists v \in son_u f_{v,1} \geq f_{v,0}]$换根即可。H不是题解做法。首先有一个暴力，用一棵线段树，每一个节点就维护对应区间的线性基，每次询问就把覆盖区间点的线性基合并即可。这样的可以过 $5 \times 10^4$ 的数据 (时限有 3s) ，复杂度：$O(60(n + q) \log n)$ 代码：Brute但是对于每一组询问都查一遍区间，其实很有冗余。比如说一个区间对应的线性基，其实对很多组覆盖这个区间的询问都要贡献。但是每次合并都很浪费，我们考虑把询问插到一棵线段树上后，可以通过计算这个区间的前后缀线性基并，然后离线回答。代码：Sol
20211007:kurumiDescription给定 $n$ 个数字串 $S_1,\dots,S_n$，每个串的长度都为 $m$。然而，现在每个字符串内部的字符顺序都可能出现随机的调换。例如若 $S_i = \mathrm{012}$ ，那么调换后 $S_i$ 会等概率随机成为 $\mathrm{012,021,102,120,201,210}$。现要把调换后的 $n$ 个数字串全部插入一棵字典树中(调换的结果是等概率随机的)，问这个字典树结点数量的期望。答案对 $998244353$ 取模。Sol不考虑 trie 的那个根节点的话，插入一个串，节点数就是串长。插入两个串，就是 $|S_1| + |S_2| - |\mathrm{lcp} (S_1,S_2)|$。这样好像可以容斥然后 dp（尹队做法）。除此之外，这还启示我们，一个串的前缀都在 trie 树上对应了一个节点。这样我们可以枚举一个字符串 $T$ ，判断 $T$ 出现在 trie 树上的概率是多少。设 $t[0 \dots 9]$ 分别表示 $T$ 中 $0 \sim 9$ 分别出现了多少次，再设 trie 树上的一个串 $S_x$ 包含了 $s[0 \dots9]$ 个 $0 \sim 9$ ，那么 $T$ 是 $S_x$ 的前缀的概率就是：$$ \LARGE{\frac{\textcolor{red}{\prod (s_i^{\underline{t_i}}) }}{\textcolor{blue}{(\sum s_i)^{\underline{\sum t_i}}}}} $$这个式子看起来就牛逼哄哄的，为了阐释它的含义，先复习一下下降幂的组合意义。$n^{\underline{k}} = \binom{n}{k} k!$ ，也就是说 $n$ 的 $k$ 次下降幂的组合意义是在 $n$ 中选 $k$ 的方案数，并且 $k$ 个东西顺序有区别。所以上式的含义可以这么理解：分母表示从 $\sum s_i$ 个数中选择 $\sum t_i$ 个数来组成一个前缀的方案数，分子为钦定每个位置为 $T$ 中对应位置的方案数。设这个概率为 $P(T,x)$ ，那么可知 $T$ 至少是一个 $S_x$ 的前缀的概率（记为 $P(T)$）为：$$ \large{P(T) = 1 - \prod\limits_{x=1}^{n} (1 - p(T,x))} $$那么我们要求的 $Ans = \sum\limits_{T} P(T)$暴力枚举 $T$ 就是 DFS 确定每一位是 $0 \sim 9$ 中的哪一个，然后对上面的式子 $O(n)$ 计算即可。注意到 $P(T)$ 之和 $t[0 \dots 9]$ 有关，而 $0 \sim 9$ 在 $T$ 中的排列情况并无直接关系。所以我们将 $P(T)$ 记做 $P(t[0 \dots 9])$ ，考虑到由这些字符构成的 $T$ 的方案数：$$ \Large{Ans = \sum\limits_{t[0 \dots 9]} \frac{\textcolor{blue}{(\sum t_i)!}}{\textcolor{red}{\prod(t_i!)}}} \times P(t[0 \dots 9]) $$复杂度：$O(m^{10} \cdot n)$再次优化，因为 $n$ 很小，试着对 $P(T)$ 进行容斥优化：$$ \Large{P(T) = \sum\limits_{\emptyset \neq S \subseteq \{1,2,\dots,9\}} (-1)^{|S|-1} \prod\limits_{i \in S} P(T,i)} $$把最后那个 $P(T,i)$ 拆开回最上面那个形式，因为 $P(T,i)$ 对于 $0 \sim 9$ 独立，上面的公式中红、蓝两部分分别与 $t_i$ 和 $\sum t_i$ 相关。可以枚举 $S$ 然后对红色的式子进行背包，蓝色部分最后算。具体做法：对 $t[0 \dots 9]$ 依次背包，加入 $t_i = y$ 时对答案的贡献是其红色部分的乘积：$\large{\textcolor{red}{\frac{\prod\limits_{j \in S} cnt_{j,i}^{\underline{y}}}{y!}}}$其中 $cnt_{j,i}$ 是 $S_j$ 中 $i$ 出现的次数。Code#include <bits/stdc++.h> #define int long long using namespace std; typedef vector < int > vec; const int SIZE = 2e2 + 5; const int mod = 998244353; int n, m; int fac[SIZE], inv[SIZE], f[SIZE], cnt[SIZE][10], pw[SIZE][SIZE]; char s[SIZE][SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } inline int readStr(char *s) { int n = 0; char c; for (n = 1; (c = fetch()) != '\n' && c != ' ' && c != EOF; ++ n) s[n] = c; return n - 1; } } using GTR::read; using GTR::readStr; int qPow(int a, int b) { int ans = 1ll; for ( ; b; b >>= 1, a = a * a % mod) { if (b & 1) ans = ans * a % mod; } return ans % mod; } void init(int N = m) { fac[0] = 1ll; for (int i = 1; i <= N; ++ i) fac[i] = fac[i - 1] * i % mod; for (int i = 0; i <= N; ++ i) { pw[i][0] = 1ll; for (int j = 1; j <= N; ++ j) pw[i][j] = pw[i][j - 1] * (i - j + 1) % mod; } } signed main() { // freopen("kurumi.in", "r", stdin); // freopen("kurumi.out", "w", stdout); n = read(), m = read(); for (int i = 1; i <= n; ++ i) { readStr(s[i]); for (int j = 1; j <= m; ++ j) ++ cnt[i][s[i][j] - '0']; } init(); int sta = (1 << n), ans = 0; for (int i = 1; i < sta; ++ i) { vec si; si.clear(); for (int j = 0; j < n; ++ j) { if ((1 << j) & i) si.emplace_back(j + 1); } int S = (int) si.size(); si.resize(S); f[0] = 1ll; for (int j = 1; j <= m; ++ j) f[j] = 0ll; for (int j = 0; j < 10; ++ j) { for (int k = 0; k <= m; ++ k) { inv[k] = qPow(pw[k][k], mod - 2ll); for (int p = 0; p < S; ++ p) inv[k] = inv[k] * pw[cnt[si[p]][j]][k] % mod; } for (int k = m; ~k; -- k) { for (int p = k - 1; ~p; -- p) f[k] = (f[k] + (f[p] * inv[k - p] % mod)) % mod; } } int answ = 0; for (int j = 0; j <= m; ++ j) { int res = f[j] * pw[j][j] % mod, p = qPow(pw[m][j], mod - 2ll); answ = (answ + (res * qPow(p, S) % mod)) % mod; } if (S & 1) ans = (ans + answ) % mod; else ans = (ans - answ + mod) % mod; } printf("%lld\n", ans % mod); return 0; }