20211007:kurumi

博主： tony102
发布时间：2021 年 10 月 07 日
2127 次浏览
暂无评论
2322字数
分类：题解

# 20211007:kurumi

## Description

给定 $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

```cpp
#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;
}
```

最后修改：2021 年 10 月 07 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

xbieygztgu
不错不错，我喜欢看 https://www.ea55.com/
ojvrnvtsvs
看的我热血沸腾啊https://www.ea55.com/
orzaztmfuh
不错不错，我喜欢看 https://www.ea55.com/
mzcwdjqqxe
不错不错，我喜欢看 https://www.ea55.com/
Yanws
牢师求更新

20211007:kurumi

tony102 • 2021 年 10 月 07 日

# 20211007:kurumi

## Description

给定 $n$ 个数字串 $S_1,\dots,S_n$，每个串的长度都为 $m$。

现要把调换后的 $n$ 个数字串全部插入一棵字典树中(调换的结果是等概率随机的)，问这个字典树结点数量的期望。答案对 $998244353$ 取模。

## Sol

这样我们可以枚举一个字符串 $T$ ，判断 $T$ 出现在 trie 树上的概率是多少。

$$
\LARGE{\frac{\textcolor{red}{\prod (s_i^{\underline{t_i}}) }}{\textcolor{blue}{(\sum s_i)^{\underline{\sum t_i}}}}}
$$

设这个概率为 $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)$ 计算即可。

$$
\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)}
$$

其中 $cnt_{j,i}$ 是 $S_j$ 中 $i$ 出现的次数。

## Code

```cpp
#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];

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;
}

20211007:kurumi

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

Luogu1641 [SCOI2010]生成字符串

Mamba in Medical Image Segmentation

Luogu1891 疯狂 LCM

Luogu3980 [NOI2008] 志愿者招募

Luogu1286 两数之和

20211007:kurumi

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

20211007:kurumi

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款